4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ For instance one contender was 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. $\endgroup$
    – Alex Meiburg
    Commented Apr 1, 2023 at 1:13
  • 3
    $\begingroup$ 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. $\endgroup$
    – abrahimladha
    Commented Apr 1, 2023 at 21:53
  • 2
    $\begingroup$ I am at a loss. A reference to what precisely? What do you mean by "an oracle for itself"? $\endgroup$
    – Andrej Bauer
    Commented Apr 2, 2023 at 14:17
  • $\begingroup$ 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. $\endgroup$
    – Alex Meiburg
    Commented Apr 2, 2023 at 17:14

0

Reset to default

Your Answer

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