# Solving the halting problem for *almost* all machines?

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

• 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. Dec 26, 2013 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.

• 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? Dec 27, 2013 at 0:20
• 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. Dec 27, 2013 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.

It can be shown that neither $$h(g,g)$$ or $$g(g)$$ halt. Hence you can solve $$g(g)$$ by building a second halting machine $$h'$$ that returns $$0$$ if input is $$(g,g)$$ and calls $$h$$ otherwise. I don't have a proof but my guess is that in general, for any program and any input, you can always construct a machine $$M$$ that tells whether it halts or not. However, there will always be some program and some input for which $$M$$ loops. To solve the problem, try to build a different halting machine $$M'$$. Given a particular program and input, the most challenging part, of course, is to figure out which halting machine is going to solve it. For some cases, it is fairly obvious but most cases remain elusive but not impossible to solve.

That was the question in my head for some time and here is my answer.

Let's consider a clever version of the miraculous machine h, call it h'. h' first examines its input (m,x) and enters an infinite loop if it somehow detects that m contains h, and then proceeds to solve the halting problem for other inputs. But then problem still remains when m contains a machine equivalent to h', and there are infinitely many such machines.

So let's move further and consider an even more clever machine h'' which first examines its input (m,x) and enters infinite loop if it detects that m contains a machine equivalent to h'', then solves halting problem for other inputs. But then, by Rice's theorem, using h'', we can build a machine which solves the original halting problem, which is impossible.

Rice's theorem makes it clear that this uncomputability phenomenon is not just limited to some small set of problematic inputs.