Lecture 13: Undecidable Languages

Diagonalization

Theorem: Every set \(S\) has cardinality strictly smaller than its powerset \(2^S\).

Proof sketch: The theorem is especially interesting for infinite sets. For concreteness, we prove it only for finite sets, but our proof would also work for infinite sets. (Exercise.) Suppose \(S=\{ 0, 1, \ldots, n\}\) for \(n\in {\mathbb N}\). We can encode every subset \(A\subseteq S\) as an \(n\)-bit string \(x_A\in \{0,1\}^n\).

Let \(x_1,\ldots,x_n\in\{0,1\}^n\) be a list of \(n\) binary strings of length \(n\). We are to show that there exists an \(n\)-bit binary string \(x\in \{0,1\}^n \setminus \{x_1,\ldots,x_n \}\) not contained in the list. Let us arrange the strings as an \(n\times n\) matrix, \[ \begin{array}{l|cccc} & 1 & 2 & \cdots & n \\ \hline x_1 & x_{1,1} & x_{1,2} & \cdots & x_{1,n} \\ x_2 & x_{2,1} & x_{2,2} & \cdots & x_{2,n} \\ \vdots & \vdots & & \ddots & \vdots \\ x_n & x_{n,1} & x_{n,2}& \cdots & x_{n,n} \end{array} \] An explicit \(n\)-bit string not in this list is the string \(\bar x_{1,1} \bar x_{2,2}\cdots \bar x_{n,n}\). The reason is that this string differs from \(x_i\) in (at least) the \(i\)-th coordinate. It follows that the number \(n\)-bit strings is larger than \(n\). \(\square\)

Existence of undecidable languages

We can use the previous theorem as a black-box to show that some languages are undecidable.

Theorem: Not every language is decidable.

Proof: The set of all Turing machines has the same cardinality as the set of binary strings \(\{0,1 \}^\ast\). On the other hand, the set of all languages is the power set of the set of binary strings. Therefore, the set of all languages has strictly larger cardinality than the set of Turing machines (by the previous theorem). Hence, there exists a language that is not decided by any Turing machine. (A Turing machine decides at most one language.) \(\square\)

Explicit undecidable language

The previous theorem shows that undecidable languages exist but it doesn’t give any hint how such languages might look like. The following theorem shows an explicit language that is undecidable.

Theorem: The following language is undecidable, \[ {L_{\mathrm{diag}}}= \{ \langle M \rangle \mid \text{$M$ on input $\langle M \rangle$ rejects} \}. \]

Proof: Every machine \(M\) fails to decide the language \(L\) on input \(w=\langle M \rangle\). If \(w\in {L_{\mathrm{diag}}}\), then \(M\) rejects \(w\). On the other hand, if \(w\notin {L_{\mathrm{diag}}}\), then \(M\) does not reject \(w\). In either case, \(M\) fails to decide \({L_{\mathrm{diag}}}\) on input \(w\). \(\square\)

Remark: In lecture 3, we have seen a non-constructive proof that some \(n\)-bit functions require large circuits, concretely size \(\Omega(2^n/n)\). The proof used the same kind of counting argument that showed the existence of undecidable languages in this lecture. Here, we managed to use diagonalization to come up with an explicit undecidable language. Exercise: Does the same kind of diagonalization give us an explicit function that requires larger circuits? Why not?