2
$\begingroup$

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?

  • 0
    @Nicolas: You are correct that you don't necessarily have to execute a program to know if it will halt or not. The key point is that executing a program is not only not *necessary*, but it is also not *sufficient*. Furthermore, Turing's proof shows that *any* method used to determine if a program halts will not be sufficient for an arbitrary program (assuming that method has the same limitations as the arbitrary program).2012-08-11

4 Answers 4

0

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.

  • 0
    @Nicolas: Turing machines are to modern day computers as ideal gases are to many gases—a good approximation that allows for many useful conclusions to be drawn. Indeed, Turing's halting problem proof applies to any computing system where the HDP has to run with the same limitations as the program being analyzed.2012-08-11
6

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.)

  • 0
    @Be$n$, Steven: Of sourse that is true. The two formulations are equivalent for the ordinary halting problems (and I'm certainly not going to claim that one of them is right and the other isn't), but they lead to different outcomes for what "the halting problem restricted to a finite set of programs" means -- which creates confusion here.2012-08-11
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$.

  • 2
    I'm glad you used the word "uniform" since uniformity is what's at the heart here. Every finite halting problem is decidable, but the collection of all finite halting problems is not uniformly decidable.2012-08-11
3

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.

  • 0
    @Nicolas: A one-element set is certainly, unambiguously, finite, but it may or may not have been that particular role in the problem you wanted to be filled by a finite set. So now you've understood why your question is ambiguous. Then it's up to you to clarify what _exactly_ you mean with "finite number of programs". Once you do that, probably either my answer or Steven's one will turn out to be the right answer to your clarified question.2012-08-11