# Halting problem for turing machines with one input

My question is:

Is there a simple construction similar to Turing's 'liar' program that shows that Turing machines plus a halting oracle cannot decide if a given Turing machine halts on all inputs.

When I talk about the liar program I am referring to the standard proof that a Turing machine can't determine the halting of all other Turing machines, since case analysis on the following leads to contradictions

def Liar(T):
if Halts('T(T)'):
loop()
else:
return


I can see that having a Halting oracle would allow me to determine if a Turing machine halts on any finite set of inputs (We would just run it all in order).

If we call regular Turing machines level 0, we can call Turing machines plus the halting oracle level 1. I have seen that the proof using the Liar program works just the same to show that level 1 machines have their own Halting problem which is undecidable for them.

• I recommend you read the relevant chapters in a textbook (e.g., Sipser). The problem you are referring to is called TM Universality, and it is not in RE nor coRE, which makes it "harder" than the halting problem (which is in RE but not coRE). Sep 7, 2020 at 19:29
• @Shaull Where is that in Sipser? I can't find it Sep 8, 2020 at 8:01
• The relevant chapters are 4 and 5. As for TM universality, you can see here: cs.stackexchange.com/questions/11411/… Sep 8, 2020 at 8:34