5.3. The Diagonal Set K

Our proof that the acceptance problem is uncomputable uses a method called diagonalization.

The goal here is to reduce diagonalization to its simplest form.

The set K

Definition. K = {‹M› | φ_M(‹M›) ≠ ⊥}

K is uncomputable

Proof. Suppose that K is computable. Select a Turing machine t that solves K. That is,

(1) φ_t(‹M›) = true  ⇔  φ_M(‹M›) ≠ ⊥

(2) φ_t(‹M›) = false  ⇔  φ_M(‹M›) = ⊥

Construct the following program F.

  F(‹M›)
    if t answers true on input ‹M›
      loop forever
    else
      return true
    end if

Notice that

φ_F(M) = ⊥
 ⇔  φ_t(‹M›) = true (by inspection of F)
 ⇔  φ_M(‹M›) ≠ ⊥

Once again, substituting M = F yields contradiction

φ_F(F) = ⊥  ⇔  φ_F(‹F›) ≠ ⊥

The name diagonalization comes from the fact that we run F on itself. If you create an infinite grid with a row for each Turing machine and a column for each input string, then the values in that table that we are interested in are on the diagonal.

  TM   s1 s2 s3 …
  M1   x
  M2      x
  M3         x
  …