Halting problem on finite set of programs

Question

As I understand the halting problem, it imply the fact that there doesn't exist one program which can answer the halting problem for every computable program and it rely on Cantor diagonalization to build the proof.

However, Cantor diagonalization would not seem to be practicable on finite set of programs.

If we are only concerned in solving the halting problem on a finite number of programs, is it still true that there are set of programs for which there exist no program that solve the halting problem?

Answer 1

If you get to choose which programs are in that finite set (e.g., all of the ones that halt) then it is trivial to create such a halting-detecting program (HDP). Otherwise, if the set of programs is arbitrary, it might as well be infinite. I.e., the set of programs being presented to your HDP is being chosen from the infinite set of all programs. This would include a theoretical program from the diagonalization. You don't get to change the program after the fact.

On a practical level, it is possible to create an HDP for a very large number of programs, but that returns the answer "don't know" for some of them. In theory, the "don't knows" would outnumber the "halts" or "doesn't halt" answers, but in practice (assuming well formed programs) it should be feasible to make that percentage fairly small.

Edit to add: As a corollary to Steven's point, any single program will have an HDP that correctly predicts whether it will halt. Consider two HDPs: one always says its input program halts, and the other one always says it doesn't halt. For any given input program, one of those two HDPs is correct.

Similarly, if we're considering the "real world" where we don't have true Turing machines but machines with a finite amount of memory (including disk space)—although if we include writing to other machines on the internet that "finite" can get quite large—then if you want an HDP that can reliably solve any program running on those machines all you need is an even bigger machine—one with $2^n$ amount of memory, where $n$ is the finite amount of memory available to the machines whose programs you're analyzing. Of course, you're also going to need a Universe with more matter than our current one has.

Answer 2

If the question is 'for every specific finite set of programs, is there a program that solves the problem on this finite set?' then the answer, perhaps surprisingly, is yes — there is such a program!

Unfortunately, the reasoning behind this is trivial: the 'answer key' for that finite set of (say) $N$ programs must be one of the $2^N$ binary strings of length $N$ (e.g., 'halts', 'halts', 'doesn't halt', 'halts', ...), and each of those $2^N$ strings is printed by some program. We don't know what program solves the problem, but we can necessarily prove that some program does.

Of course, if you want your program to work for 'any' finite set then (as Ben's answer suggests) the problem is every bit as hard as the core halting program; to be able to do that, you'd need to be able to pass in the indices of the programs to test, and this is equivalent to knowing the answer for each program (or, viewed another way, having a program that takes in an index for a program — e.g., its source code — and tells you whether that program halts or not.)

Answer 3

Let $\Phi_e$ denote the $e^\text{th}$ Turing machine. One form of the Halting problem is that the set $\{e : \Phi_e(e) \text{ halts }\}$ is not computable. It is good exercise to show that this Halting Problem is equivalent to whatever form of the halting problem you are using.

If fixed finitely many Turing Machines $F = \{e_0, e_1, e_2, ..., e_n\}$, then there exists finite subsets $F_0, F_1 \subseteq F$ such that for all $e \in f_0$, $\Phi_e(e)$ does not halt and for all $e \in F_1$, $\Phi_e(e)$ converges. Then you can define a computable function

$\Psi(n) = \begin{cases} 1 & \quad e \in F_1 \\ 0 & \quad e \in F_0 \\ 0 & \quad \text{ otherwise } \end{cases}$

Since $F, F_0, F_1$ are all finite, you can make a Turing Machine that compute $\Psi$. Hence $\Psi$ is a Turing Machine (or computable function) that tells the answer to the Halting Problem for the particular finite set $\{e_0, e_1, ..., e_n\}$.

Note that this process is not uniform. If you fixed $F$, there exists a Turing machine that $\Psi_F$ that tell you the answer for $F$. However, there is not computable function taking input $F$, will give you computably $\Psi_F$. This is because given $F$, there is not computable procedure to tell you what $F_0$ and $F_1$ are. In the case that you fixed a particular $F$, it was good enough just to know that there exists finite sets $F_0$ and $F_1$ that works for this particular $F$.

Answer 4

There are finite sets of programs for which the halting problem is undecidable.

One example of this would be a set whose only element is a program that happens to be an interpreter for a Turing-complete language.

There can be no restricted halting-decider for that single program, because that would effectively be an unrestricted halting-decider for the language being interpreted -- which, again, can be shown to be impossible using standard diagonalization.