1

$D$ is decision problem whose inputs are the natural numbers.

Suppose $A$ is an algorithm to solve $D$ in which we know that it is:

  • partially correct for all inputs
  • halts on all inputs >= 1000.

Can I deduce that $D$ is decidable?

On the one hand, the number of inputs that are unknown is finite, so maybe we can precompute the results of $D$ on those 1000 inputs and for all others use $A$? On the other hand, it seems like it might be possible to reduce the Halting Problem to $D$ somehow? I'm not sure.

Thanks!

chrisg
  • 13

1 Answers1

0

It is decidable, even if we do not know the answers for numbers $\lt 1000$. Let $K$ be any finite set. There is an algorithm for $K$. Any program that halts and says yes on elements of $K$ and halts and says no for non-elements of $K$ will do. There is such a program, even if we happen not to know what that program is.

So let $D_0$ be the part of $D$ that is less than $1000$, and let $D_1$ be the part $\ge 1000$. There is an algorithm $B$ for $D_0$, even if we don't know what it is. On any input, run $B$ if the input is $\lt 1000$, and run $A$ if the input is $\ge 1000$.

André Nicolas
  • 507,029