<p>Starting with a basic Turing machine, successive applications of the Turing jump produce successively more powerful machines, that can be indexed by any ordinal. A tempting error for students, and one I've heard a few times, is something like:</p>
<blockquote>
<p>Well, I'll define a class M of machines, defined by the standard Turing machine operations and having an oracle O. When O is queried with an integer x, O decodes x as a description of an M-machine and returns whether that M machine halts on an empty input string. This way any M machine can solve the halting problem of any other M machine -- it can solve its own Halting problem!</p>
</blockquote>
<p>This is of course incorrect, since you can logical paradoxes from it: a machine simply needs to ask O about itself and then perform the opposite. This is a different theorem from the standard &quot;a Turing machine can't solve its own Halting problem&quot; issue, it's that you <em>also can't define anything more powerful than a Turing machine</em> that is a fixed point of the Turing jump.</p>
<p>I've heard this argument repeated and it seems like folklore. However, I would very much like a reference to it. My background is not so much in computability theory and I know there's a lot I don't know. If anyone could point me to an early description of this idea (theorem?), it would be greatly appreciated.</p>

CC BY-SA 4.0
2023-04-01T01:13:41.810Z
For instance one contender was https://www.jstor.org/stable/3109884, which seems to discuss self-reference in general and the Halting problem, but only discusses them on Turing machines without oracles. A good reference would make clearer reference to Turing jumps and halting oracles.
Alex Meiburg
CC BY-SA 4.0
2023-04-01T21:53:05.820Z
This seems slightly related to the Kleene's Recursion theorem. A Turing machine may obtain a copy of its own description and compute with it. It may even simulate itself. This is useful to quickly prove languages undecidable. For example assume to the contrary HALT has decider H. M on input w obtains <M>, queries decider H with <M,w> and returns the opposite. Then M does the opposite of what H says it does, a contradiction. I Would look at 6.1 of Sipser, but it says nothing about oracles.
abrahimladha
CC BY-SA 4.0
2023-04-02T14:17:10.613Z
I am at a loss. A reference to what precisely? What do you mean by "an oracle for itself"?
Andrej Bauer
CC BY-SA 4.0
2023-04-02T17:14:04.897Z
I want a reference for the fact that you cannot have a Turing machine with an oracle for itself: a machine with an oracle O, where O is a halting oracle for "Turing machines with an O oracle". It is logically inconsistent to try to do so.

If your gut reaction is "you can't have a halting oracle for yourself, just like you can't have a set A of all things not in A, that's not how set theory works" -- great! That's precisely the problem. But it's something that people try to do anyway, and I was hoping for a reference to the fact that this is verboten.
Alex Meiburg
<reference-request><computability><halting-problem>
Reference for "A Turing machine cannot be equipped with an oracle for itself"
Alex Meiburg
# Reference for "A Turing machine cannot be equipped with an oracle for itself"

(Asked by: username_0 on 2023-04-01)

Starting with a basic Turing machine, successive applications of the Turing jump produce successively more powerful machines, that can be indexed by any ordinal. A tempting error for students, and one I've heard a few times, is something like:

> Well, I'll define a class M of machines, defined by the standard Turing machine operations and having an oracle O. When O is queried with an integer x, O decodes x as a description of an M-machine and returns whether that M machine halts on an empty input string. This way any M machine can solve the halting problem of any other M machine -- it can solve its own Halting problem!

This is of course incorrect, since you can logical paradoxes from it: a machine simply needs to ask O about itself and then perform the opposite. This is a different theorem from the standard "a Turing machine can't solve its own Halting problem" issue, it's that you *also can't define anything more powerful than a Turing machine* that is a fixed point of the Turing jump.

I've heard this argument repeated and it seems like folklore. However, I would very much like a reference to it. My background is not so much in computability theory and I know there's a lot I don't know. If anyone could point me to an early description of this idea (theorem?), it would be greatly appreciated.

**Tags:** reference-request, computability, halting-problem
> **Comments:**
> **username_0**: For instance one contender was https://www.jstor.org/stable/3109884, which seems to discuss self-reference in general and the Halting problem, but only discusses them on Turing machines without oracles. A good reference would make clearer reference to Turing jumps and halting oracles.  
> **username_1**: This seems slightly related to the Kleene's Recursion theorem. A Turing machine may obtain a copy of its own description and compute with it. It may even simulate itself. This is useful to quickly prove languages undecidable. For example assume to the contrary HALT has decider H. M on input w obtains <M>, queries decider H with <M,w> and returns the opposite. Then M does the opposite of what H says it does, a contradiction. I Would look at 6.1 of Sipser, but it says nothing about oracles.  
> **username_2**: I am at a loss. A reference to what precisely? What do you mean by "an oracle for itself"?  
> **username_0**: I want a reference for the fact that you cannot have a Turing machine with an oracle for itself: a machine with an oracle O, where O is a halting oracle for "Turing machines with an O oracle". It is logically inconsistent to try to do so.  If your gut reaction is "you can't have a halting oracle for yourself, just like you can't have a set A of all things not in A, that's not how set theory works" -- great! That's precisely the problem. But it's something that people try to do anyway, and I was hoping for a reference to the fact that this is verboten.  

---

## 0 answers

