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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Can't you concatenate the finite set of programs into one program? i.e. Run the first program. If the first program halts run the second program. If the second program also halts run the third program. etc. $\endgroup$ – Jay Aug 10 '12 at 23:21
  • $\begingroup$ @Jay: That will only tell you if all of the programs halt or if at least one of them doesn't. For example, it wouldn't tell you that 2 of them halted and 3 of them didn't. And of course, if the program doesn't halt, how do we know that it doesn't halt without waiting an infinite amount of time? $\endgroup$ – Ben Hocking Aug 11 '12 at 1:42
  • $\begingroup$ @Ben: I read a similar argument in Turing's paper and it is not convincing. The fact is you don't have to execute a program to know if it will halt or not. A similar example is a program that compute a function with a limit to infinity. It is possible to calculate the limit value without actually calculating every values of the function up to infinity. Isn't the halting problem similar to this kind of problem? $\endgroup$ – Nicolas Aug 11 '12 at 13:44
  • $\begingroup$ @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). $\endgroup$ – Ben Hocking Aug 11 '12 at 14:37
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Then that seems to imply that every halting problem that we will ever encounter is solvable, which seems to contradict non-solvability of halting problem. How is it possible? $\endgroup$ – Nicolas Aug 10 '12 at 23:26
  • $\begingroup$ @Nicolas: It does not imply that. There are programs that have actually been written with an intent (instead of just a "random program") that analyzers are unable to determine whether they will halt. If one needs to determine if such a program will halt the typical method is to alter the program in such a way to make it more obvious, but then one has failed to prove whether the original program would halt. $\endgroup$ – Ben Hocking Aug 11 '12 at 1:26
  • $\begingroup$ I would really be interested to have examples if you can direct me to some references. $\endgroup$ – Nicolas Aug 11 '12 at 2:07
  • $\begingroup$ @Nicolas: The idea I had is any C++ compiler. C++ templates are Turing complete. (cpptruths.blogspot.com/2005/11/…) However, compilers like to know that they will halt, so ANSO/ISO C++ conforming programs are required to limit their template substantiation depth to 17. One can, however, write non-conforming programs and tell gcc to compile them anyway. (See -ftemplate-depth-n at linux.die.net/man/1/gcc) $\endgroup$ – Ben Hocking Aug 11 '12 at 12:16
  • $\begingroup$ Thanks, I'm not much proficient with c++ templates I will have to study it a bit more. Maybe this is starting to stretch further than the original question though, but every such example which are given seems would be refuted like this: "yes but with a human given enough time and resource, a program could eventually be written for every explicit case." Since I find it very difficult not seeing humans as very sophisticated Turing machines, this is bugging me a lot. $\endgroup$ – Nicolas Aug 11 '12 at 13:01
6
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ But as I responded to Ben, wouldn't it be contradictory since every halting problem we would ever encounter be solvable? $\endgroup$ – Nicolas Aug 10 '12 at 23:34
  • $\begingroup$ Nicolas: The individual halting problem is solvable - for any given program, the answer is 'yes' or 'no'. But what one traditionally considers as the halting problem is computing the halting function - one that takes a machine code and returns a yes/no query. I think the distinction you might be missing is the one between a problem being solvable and being able to actually know the solution. These two aren't the same thing! $\endgroup$ – Steven Stadnicki Aug 10 '12 at 23:39
  • $\begingroup$ Thanks, your precisions are helpful. I just can't put away that contradictory weird feeling however... I guess I'll just accept it as it is for now! $\endgroup$ – Nicolas Aug 10 '12 at 23:47
  • $\begingroup$ This appears to assume that the "halting problem" is to decide whether a given program will halt when given the empty input. $\endgroup$ – Henning Makholm Aug 11 '12 at 0:49
  • $\begingroup$ @HenningMakholm True, but fortunately that is (by standard coding techniques) a valid form of the halting problem. $\endgroup$ – Steven Stadnicki Aug 11 '12 at 2:08
3
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Quinn Culver Aug 11 '12 at 4:54
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ That's interesting. I feel that kind of program would be way too much abstract, or generic to be of any concrete practicality though. It is so general that no one can even tell what exactly this program is trying to solve, until some more traditional program is loaded into it. $\endgroup$ – Nicolas Aug 11 '12 at 2:04
  • $\begingroup$ Thinking about it, the set you describe has a quirky recursive pattern. Is it really a true finite set? It appears so because the only explicit element in it is the interpreter, but then to really answer the halting problem you must ask the question for every possible interpretable program which are infinite then. Is the set the interpreter or is it the interpretable programs? $\endgroup$ – Nicolas Aug 11 '12 at 14:26
  • $\begingroup$ @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. $\endgroup$ – Henning Makholm Aug 11 '12 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.