Undecidabilty and Unrecognizability by Diagonalization

As mentioned earlier, it turns out that $A_{TM}$ is undecidable so there are undecidable problems. Worse than that, there actually are problems that are not even recognizable!

We begin by showing that there exists a language that is not recognizable. The idea is to show that there are more languages than there are Turing machines and thus there is a language that is not recognized by any Turing machine. But the set of languages is infinite and so is the set of Turing machines, so first we need a way to compare the sizes of infinite sets.

To compare the sizes of finite sets, we can simply count the number of elements in both sets and then compare the counts. We cannot do this for infinite sets. However, observe that another way to show that two finite sets $A$ and $B$ have the same size is by showing that we can match each element of $A$ to a unique element of $B$ . If the sets have different sizes, there is no such matching.

Fortunately, this idea of matching extends to infinite sets. Formally, the matching is given by a function $f : A \rightarrow B$ that maps elements in $A$ to elements in $B$ . The function $f$ is a 1-1 correspondence if it satisfies:

(Injectivity) No two elements in $A$ get mapped to the same element in $B$ . Formally, for every $x,y \in A$ , we have $f(x) \neq f(y)$ .
(Surjectivity) Every element in $B$ is mapped to by some element in $A$ . Formally, for every $z \in B$ , there is a $x \in A$ such that $f(x) = z$ .

We say that two sets $A$ and $B$ have the same size iff there is a 1-1 correspondence $f: A \rightarrow B$ . Moreover, if set $A$ has the same size as the set of natural numbers $\mathcal{N} = \{1, 2, 3, \ldots\}$ , then we say that $A$ is countable.

7.2.1Countable sets¶

7.2.2Diagonalization for Reals¶

To show that there are more languages than Turing machines, we will use a technique called diagonalization. First, we present the technique in a simpler setting and use it to show that the set of real numbers $\mathcal{R}$ is uncountable. Thus the set of reals is larger than the set of natural numbers.

Proof 3

We will show that every function $f : \mathcal{N} \rightarrow \mathcal{R}$ misses some real number, i.e. is not surjective: there exists $x \in \mathcal{R}$ such that for every $n \in \mathcal{N}$ , $f(n) \neq x$ .

Consider a function $f : \mathcal{N} \rightarrow \mathcal{R}$ . Define the real number $x$ as follows: for every $i \geq 1$ , $x$ differs from $f(i)$ in the $i$ -th decimal place.

Illustration of construction of $x$ given $f$ . It is called “diagonalization” because $x$ is defined by the diagonal of the table.

This is a valid definition of a real number. By definition, $f(n) \neq x$ for every $n \geq 1$ and so $f$ is not a 1-1 correspondence.

Since this argument holds for every function $f : \mathcal{N} \rightarrow \mathcal{R}$ , we get that there is no 1-1 correspondence between $\mathcal{N}$ and $\mathcal{R}$ and so $\mathcal{R}$ is uncountable.

7.2.3Diagonalization for Languages¶

Proof 4

Fix an encoding of Turing machines into strings. Let $M_i$ be the $i$ -th Turing machine in string order of its encoding, and $w_i$ be the $i$ -th Boolean string in string order.

Define the language $L_D = \{w_i \mid w_i \notin L(M_i)\}$ , i.e. $L_D$ disagrees with $L(M_i)$ on $w_i$ and is not recognized by $M_i$ .

Illustration of construction of $L_D$ . In this diagram, “in” means the string is in the language of the corresponding row, and “out” means it is not in the language.

This is a valid definition of a language. Since every Turing machine has an encoding into a finite-length string, every Turing machine is $M_i$ for some $i$ . Since $L_D$ is not recognized by any $M_i$ , it is not recognizable.

7.2.4Undecidability of TM Acceptance¶

We can now show that $A_{TM}$ is undecidable by showing that a decider for $A_{TM}$ gives a decider for $L_D$ which is impossible since $L_D$ is not even recognizable.

Proof 5

We first show that if there exists a decider $U$ for $A_{TM}$ , then we can construct a TM $D$ that decides $L_D$ .

On input w:
  Compute i such that w = w_i
  Run U on <M_i, w>
  Accept if U rejects
  Reject if U accepts

Since $U$ is a decider, it always accepts or rejects, it never runs forever. Thus, $D$ also always halts. Moreover, for every string $w_i$ , $D$ accepts it if and only if $M_i$ does not accept $w_i$ . Therefore, $L(D) = L_D$ and so $D$ decides $L_D$ .

Since $L_D$ is not recognizable and thus not decidable, we conclude that $A_{TM}$ is not decidable.

Models of Computation

Turing Machine Acceptance Problem