4
$\begingroup$

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.

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Belatedly, welcome to CS! $\endgroup$ Commented Aug 30, 2018 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$ Commented Aug 30, 2018 at 16:39
  • $\begingroup$ @antimornings Yup. See my edit. $\endgroup$ Commented Aug 30, 2018 at 19:19
7
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Commented Aug 30, 2018 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$ Commented Aug 30, 2018 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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