Halting problem for turing machines with one input

Question

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.

Answer 1

What you call a "liar" program is typically called a diagonalization argument, since it somehow resembles Cantor's diagonalization argument.

Usually what we mean by that is that if we try to enumerate all elements with a certain property, then we can point out, by construction, an element that is necessarily "incorrect", and we do so by showing that it does not satisfy the property with regards to itself (this is completely hand-wavy, but if you've seen the argument, you'll hopefully understand what I mean).

Now, what you're asking is whether we can do the same in order to show that ALL_TM (TM universality) is not decidable by a TM with oracle to HALT_TM.

Well, not really. At least not in a natural way: the argument would have to start by assuming there exists an oracle machine M that decides ALL_TM, and then constructing from M some other machine N (what you call a "liar" machine), which would yield a contradiction when we run N on N. However, the machine N would have to be an oracle machine, not a standard TM (or you would essentially lose the power of the oracle in M). But since the oracle in N takes as input standard TMs, then the inner working of N would somehow need to create a standard TM to feed to the oracle. This doesn't seem like a natural construction, and it would certainly not be simple.

Now, perhaps there is some convoluted way of giving a direct diagonalization argument for this claim, but it's not well motivated, given that proving the claim directly (namely that ALL_TM is not decidable by a TM with oracle to HALT) is not difficult using standard tools, such as reductions.