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)'):

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.

  • 3
    $\begingroup$ 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). $\endgroup$ – Shaull Sep 7 at 19:29
  • $\begingroup$ @Shaull Where is that in Sipser? I can't find it $\endgroup$ – rain1 Sep 8 at 8:01
  • 1
    $\begingroup$ The relevant chapters are 4 and 5. As for TM universality, you can see here: cs.stackexchange.com/questions/11411/… $\endgroup$ – Shaull Sep 8 at 8:34

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.

| cite | improve this answer | |
  • $\begingroup$ That is a great explanation of why we couldn't just give a simple construction that proves this separation. Thanks. What are reductions? $\endgroup$ – rain1 Sep 9 at 16:28
  • 1
    $\begingroup$ Reductions are a way of transforming one problem to another, in such a way that if one is known to be undecidable, then you can deduce the same for the other. You can read e.g. Sipser Chapter 5. Also, since you seem interested in this stuff, why not take a course (online or physical) about computability? There are many such courses, and since this stuff is being taught for some decades, the material is very polished and usually fun to listen to. $\endgroup$ – Shaull Sep 9 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.