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:Query the oracle for $A'_{TM}$ with $\langle M, w \rangle$.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.Check if $M$ is an oracle TM with an oracle for $A'_{TM}$. If it is not, reject. Otherwise, proceed to the next step.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.
Can a Turing machine be both decidable and undecidable relative to itself?
turing machines;undecidability;oracle machines
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.