3
$\begingroup$

Consider the language:

$A'_{TM} = \{\langle M,w\rangle: M \mbox{ is a TM with access to an oracle for } A_{TM} \mbox{ and } M \mbox{ accepts } w\}$

Clearly, we expect that any language is decidable relative to itself, including $A'_{TM}$. So let $F$ be an oracle decider for $A'_{TM}$ that has access to an oracle for $A'_{TM}$. In particular, we can construct $F$ as follows.

$F = $ "On input $\langle M, w \rangle$, where $M$ is a TM and $w$ is a string:

  1. Query the oracle for $A'_{TM}$ with $\langle M, w \rangle$.

  2. If the oracle replies YES, accept. If the oracle replies NO, reject."

Now, consider the following TM, $D$.

$D$ = "On input $\langle M \rangle$, where $M$ is a TM.

  1. Check if $M$ is an oracle TM with an oracle for $A'_{TM}$. If it is not, reject. Otherwise, proceed to the next step.

  2. Simulate $F$ on $\langle M, M \rangle$. If it accepts, reject. If it rejects, accept."

Now, suppose that we feed $\langle D \rangle$ as input to $D$. Then clearly, computation proceeds to Step 2, since $D$ has an oracle for $A'_{TM}$. But Step 2 yields a contradiction, since we are forced to conclude that $D$ accepts $\langle D \rangle$ if and only if $D$ rejects $\langle D \rangle$. So it seems we must conclude that $A'_{TM}$ is both decidable and undecidable relative to itself, which seems absurd.

$\endgroup$
4
$\begingroup$

A Turing machine doesn't come with an oracle. The oracle comes from outside. Rather, an oracle Turing machine is a Turing machine that has a special way of accessing an oracle. When you run the Turing machine with a specific oracle $O$, whenever the machine activates the special mechanism for accessing an oracle, you forward the request to $O$. A phrase like "$M$ is an oracle TM with an oracle for $A'_{TM}$" is thus meaningless.

You are saying that you run $D$ on the input $\langle D \rangle$, but you haven't specified what oracle you are running $D$ with. If you want $F$ to have the proper semantics, then you have to run $D$ with an oracle for $A'_{TM}$. When run in this way, $D$ accepts $\langle D \rangle$ iff $F$ rejects $\langle D,D \rangle$ when run with $A'_{TM}$, and so iff $D$ rejects $\langle D \rangle$ when run with $A_{TM}$.

Notice that there is no contradiction: $D$ accepts $\langle D \rangle$ when run with the oracle $A'_{TM}$ iff it rejects $\langle D \rangle$ when run with the oracle $A_{TM}$.

The real reason this works out is that a machine cannot get as input an oracle TM together with an oracle, since the oracle is an infinite object and so it cannot be specified as input.

$\endgroup$
  • $\begingroup$ It looks like I have a misunderstanding of oracle TMs. Is every oracle TM a Turing machine, or is every Turing machine an oracle TM? Sipser's definition (in his Intro to the Theory of Computation textbook) of an Oracle TM is very informal. $\endgroup$ – user95224 Feb 28 '17 at 4:54
  • $\begingroup$ Also, I am using Sipser's terminology when he writes, for instance, "an oracle Turing machine with an oracle for $A_{TM}$..." $\endgroup$ – user95224 Feb 28 '17 at 5:05
  • 1
    $\begingroup$ An oracle Turing machine is a Turing machine which has some mechanism allowing it to access an oracle. When you run the machine, you have to specify an oracle. When Sipser writes "an oracle Turing machine with an access to an oracle for $A_{TM}$ can do X", he means an oracle Turing machine which can do X if the oracle it is run with is $A_{TM}$. $\endgroup$ – Yuval Filmus Feb 28 '17 at 5:10
  • 2
    $\begingroup$ Generally speaking, Turing machines and oracle Turing machines can be specified in full using a finite string, whereas an oracle cannot. That's why it has to be supplied from the outside. $\endgroup$ – Yuval Filmus Feb 28 '17 at 5:11
  • 1
    $\begingroup$ Oracle Turing machines and ordinary Turing machines are two different machines, just like DFAs and NFAs. Every ordinary Turing machine has a corresponding oracle Turing machine that never accesses the oracle. To say anything more, you'll have to fix a particular encoding, and then you can try to prove or disprove your claim. $\endgroup$ – Yuval Filmus Feb 28 '17 at 5:18

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.