# Oracle machine solving halting problem for other oracle machines

Could someone give me a simple explanation why an oracle machine that can solve the halting problem for standard Turing machines, is however unable to solve the halting problem for other such oracle machines?

I have tried searching for the answer online but could not find any that really answered the question.

Remember that an oracle machine isn't really a "complete object" - basically anything interesting we might ask of it depends on what oracle we feed it. For example, whether an oracle machine $\Phi_e^-(e)$ halts or not depends in general on what oracle it's working with.

So let me rephrase the fact you're starting with:

There is an oracle $X$ and an oracle machine $\Phi_e^-$ such that $\Phi_e^X$ (= $\Phi_e^-$ with oracle $X$) computes the halting problem.

Now every specific oracle has a corresponding halting problem: namely, given an oracle $X$ we let $$X':=\{e: \Phi_e^X(e)\mbox{ halts}\}.$$ The usual proof that the halting problem is not computable translates immediately to prove that $X'$ is not $X$-computable - that is, for every oracle $X$, there is no oracle machine $\Phi_e^X$ such that $\Phi_e^X$ computes $X'$.

Since $X'$ depends heavily on $X$, there is no "halting problem for oracle machines" - rather, each oracle determines a different "relativized halting problem," and the more complicated we make the oracle the more complicated this becomes, with the result that we never "catch our tail."

EDIT: here's how to "relativize" the unsolvability of the halting problem:

Fix an oracle $X$. Suppose $c$ "solves the $X$-halting problem" - that is, for each $n$ we have $\Phi_c^X(n)=1$ iff $n=X'$. As in the non-oracle case, there is$^*$ an oracle machine $\Phi_e^-$ such that for all $n$, we have $\Phi_e^X(n)\downarrow$ iff $\Phi_c^X(n)\downarrow=0$. Then $\Phi_c^X(e)=0$ iff $e\in X'$, contradicting the assumption on $c$.

$^*$This uses the relativized version of the existence of a universal machine, which is proved analogously as for non-oracle machines. Note, incidentally, that $e$ is independent from $X$: a single $e$ does the job for every oracle.

• Belatedly, welcome to CS! Aug 30 '18 at 15:57
• How would we adapt the original proof of the halting problem to this oracle machine? Similarly program the oracle machine such that if the oracle predicts it halts, then loop forever and vice versa? Aug 30 '18 at 16:39
• @antimornings Yup. See my edit. Aug 30 '18 at 19:19

The proof that a Turing machine with an oracle for $X$ can't solve the halting problem for Turing machines with an oracle for $X$ is identical to the proof that an ordinary Turing machine can't solve the halting problem for ordinary Turing machines.

• So we would simply say that we program oracle machine such that, if it predicts it will halt, it then loops forever and vice versa? Aug 30 '18 at 16:40
• Basically, yes. Just go through the proof and replace "Turing machine" with "Turing machine with an oracle for X" and "halting problem" with "halting problem for Turing machines with oracles for X." Aug 30 '18 at 17:07

For me, the halting problem is entirely artificial. The whole point is that there is one and only infinite Turing machine that can't decide whether the same infinite Turing machine will stop on given problem.

But real computers always have limited memory. And practically speaking, we don't expect that computer with 1 MB of memory will solve the halting problem for any program using entire MB of memory. It needs some more memory to store its own data.

And the halting theorem proof doesn't say anything about using 2 MB machine to prove that 1 MB machine will stop on given program.

And that's all about it. The halting theorem proves very obvious thing about real computers - that computer can't check itself because it doesn't have enough resources. Once you differentiate between checking and checked computers, the proof don't work anymore.

• "there is one and only infinite Turing machine" There is no such thing as an "infinite Turing machine". If you wish to define one, then fine, but the question is not asking about those. Aug 30 '18 at 13:37
• @DavidRicherby the Turing machine is infinite Aug 30 '18 at 13:57
• The Turing machine has access to an unbounded tape. The machine itself is finite and there will only ever be a finite amount of data written on the tape. In any case, the question isn't asking for a critique of the halting problem; it's asking why a specific problem is undecidable in a specific model of computation. Aug 30 '18 at 13:59
• The halting problem is based on no such thing. And this question is asking about machines that can solve undecidable problems. It has nothing to do with physical machines. Aug 30 '18 at 20:02
• I don't see how this answers the question. The question asks how to prove something about the halting problem. This answer seems to be arguing that the question is artificial and uninteresting. Well, maybe, or maybe not -- but either way, it's not an answer to the question. Am I misunderstanding something?
– D.W.
Aug 30 '18 at 22:46