As I understand it, the proof of the halting problem’s undecidability is conceptually pretty simple. You postulate a machine $h(m, x)$ which (1) always halts and (2) returns 1 if $m$ halts with input $x$, 0 if not. Using this, you build a machine $g(m)$ that spins forever if $h(m, m) = 1$, and halts if $h(m, m) = 0$. Then, $g(g)$ creates a contradiction: if it halts, then $h(g, g) = 1$ and $g(g)$ must spin forever; and similarly, if spins forever, it must halt.

So my question is: does this say anything about the halting problem for machines other than those that solve the halting problem or use machines that solve it? That is, couldn’t you still build a machine $h’(m, x)$ that solves the halting problem for any machine except $h$, $h'$, and any machine that includes $h$ or $h'$? With that restriction, you can’t evaluate $g(g)$, and the contradiction goes away. It seems like such a machine would still be extremely powerful.

Or does the math behind my loose understanding of the proof-of-undecidability preclude this? One way I could imagine this happening is if the precise definition of "except any machine…" can be proved to be not-halting, in which case the answer to my question is basically that the existence (or definition?) of $h'$ is not decidable.

I am not super well-versed in this branch of mathematics, so an "explain it like I'm 5"-type answer would be much appreciated!

(Apologies if this is a dup; I searched for other halting problem questions and couldn't find and answer, though I'm not sure what to add to focus the search. This seems similar to, but different from, this question.)

  • 2
    $\begingroup$ I recall reading a paper about how for a random Turing machine, halting problem is decidable with probability $1$. Although that's just another way to say that most Turing machines are boring. $\endgroup$ – Karolis Juodelė Dec 26 '13 at 23:57

The theorem says that there is no algorithm that solves the halting problem for all Turing machines. There are certainly algorithms that solve the halting problem for some subclasses of machines. However your criterion is not well stated. There are other problems for which it is known that algorithms do not exist, e.g. the word problem for groups, or existence of solutions of diophantine equations. Halting for Turing machines that search for solutions of these is also undecidable.

  • $\begingroup$ Is the proof of those other problems' undecidability different from the proof of the general halting problem's undecidability? That is, do we just have to take each kind of problem one at a time, determining if a general halting algorithm can be created for it? $\endgroup$ – yshavit Dec 27 '13 at 0:20
  • 1
    $\begingroup$ Typically an undecidability proof might involve some sort of "encoding" of a problem known to be undecidable into a different form. Thus the undecidability of Diophantine equations (Hilbert's 10th problem) was proven by showing that all recursively enumerable sets are Diophantine. $\endgroup$ – Robert Israel Dec 27 '13 at 1:06

I'm not going to answer the question, because I don't know what the correct answer is. I'm just trying to reformulate it so that it can receive a precise answer from someone. The term 'include' in the original question may lack the required precision for the question to have a definite answer.

The usual proof that the Halting Problem is unsolvable employs a form of diagonalization: we assume the existence of the machine H that solves the problem and then we construct another machine D for which H won't always work; the point is that D is constructed by reference to H itself: D is so defined that H, when fed D's code, would have to behave otherwise than it behaves on that input. D is defined in such way that its computations are logically related to H's.

Suppose we want to restrict ourselves to considering only those computations that are unrelated to H's behavior in the sense that they cannot be defined in terms of H's behavior. For this limited problem the classical proof doesn't go through. So the question arises: can such an H exist, which is successful for all computations in the restricted range even if it doesn't work for all possible computations?

An answer in the affirmative would perhaps imply that computations can be accommodated in a hierarchy of levels such that for any level n, there is a machine some of whose computations are of level greater than n and which solves the Halting Problem for all computations of level n.

I am not sure my own terms ('can be defined in terms of') are any more precise than the original 'include' but perhaps they are.


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.