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.

  • 1
    $\begingroup$ Belatedly, welcome to CS! $\endgroup$ – David Richerby Aug 30 '18 at 15:57
  • $\begingroup$ 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? $\endgroup$ – antimornings Aug 30 '18 at 16:39
  • $\begingroup$ @antimornings Yup. See my edit. $\endgroup$ – Noah Schweber 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.

  • $\begingroup$ 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? $\endgroup$ – antimornings Aug 30 '18 at 16:40
  • $\begingroup$ 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." $\endgroup$ – David Richerby 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.

  • 2
    $\begingroup$ "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. $\endgroup$ – David Richerby Aug 30 '18 at 13:37
  • $\begingroup$ @DavidRicherby the Turing machine is infinite $\endgroup$ – Bulat Aug 30 '18 at 13:57
  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby Aug 30 '18 at 13:59
  • $\begingroup$ @DavidRicherby hint - how much space will occupy Turing machine, including the tape? The halting problem theorem is based on the assumption that there is one and only Turing machine, while physical computers may have various memory sizes, and the proof is useless to them (i.e. you can only prove that 1 MB computer can't decide halting for very same computer). The oracle computer mentioned in the question is just abstraction of an idea that really there are many computer sizes and larger computer may be able to solve halting problem for a lesser one. $\endgroup$ – Bulat Aug 30 '18 at 18:37
  • 2
    $\begingroup$ 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? $\endgroup$ – D.W. Aug 30 '18 at 22:46

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.