5.2. The Acceptance Problem for Turing Machines

We are ready to find an uncomputable problem.

On the preceding page, we asked if it is computable to determine whether a given DFA accepts a given string.

This time, we ask a similar question about a Turing machine (or any program in a sufficiently general model of computing).

Proof. The reasoning is by contradiction. Assume that ACCEPT_TM is computable. It will suffice to derive a contradiction.

Since, by assumption, ACCEPT_TM is computable, there must be some Turing machine A that solves it. That is,

(1) φ_A(‹M›, s) = true  ⇔  φ_M(s) = true

(2) φ_A(‹M›, s) = false  ⇔  φ_M(s) ≠ true

Let's build another Turing machine (or, if you prefer, program) F that takes just a Turing machine M as its argument. Since we have A in hand, we can use it to build F.

  F(‹M›)
    If A answers true on input (‹M›, ‹M›) then
      loop forever
    else
      return true
    end if    

Notice

φ_F(‹M›) answers true
 ⇔  φ_A(‹M›, ‹M›) ≠ true (*)
 ⇔  φ_M(‹M›) ≠ true (by fact (1) above)

(*) From inspection of the definition of F and the fact that A must stop on every input.

But that reasoning holds for every M. In particular, it holds when M = F! Substituting M = F into that equivalence yields

φ_F(‹F›) true  ⇔  φ_F(‹F›) ≠ true

That is nonsense. No value can be true if and only if it is not true.

That contradiction proves the theorem. ◊

Notice that the proof is actually quite constructive. If you give me a program A that claims to solve ACCEPT_TM, then I build F and give you (‹F›, ‹F›) as an input on which A gives the wrong answer, since

F accepts ‹F›  ⇔  A rejects (‹F›, ‹F›)

If F accepts ‹F›, then A says that it doesn't. If F does not accept ‹F›, then A says that it does.