Turing Machines

Example:

Consider a language \[ L_1 = \{0^{2^n} \mid n \geq 0\} \] which generates all strings of \(0\)s whose length is a power of 2.

A Turing machine \(M_1\) must decide \(L_1\):

\(M_1 = \) "On input string \(w\): "

1. Read left to right across the tape, crossing out every other \(0\).
2. If in Stage 1, the tape contained a single \(0\), accept.
3. If in Stage 1, the tape contained more than a single \(0\) and the number of \(0\)s was odd, reject.
4. Return the head to the left-hand end of the tape.
5. Go back to Stage 1."

Note: in the state diagram below, Stage 1's "crossing out every other \(0\)" is realized by first replacing the leftmost \(0\) with a blank \(\sqcup\) (which serves as the left-end marker the head later returns to in Stage 4) and then replacing every other subsequent \(0\) with an "x". The trace that follows illustrates exactly this behavior.

\(Q = \{q_1, q_2, q_3, q_4, q_5, q_{\mathrm{accept}}, q_{\mathrm{reject}}\}, \, \Sigma = \{0\}, \, \Gamma = \{0, \text{ x }, \sqcup\}\), and the state diagram is as follows:

For example, if input is \(0000\), the sequence of configurations is as follows \[ \begin{align*} &q_1 0 0 0 0 \vdash \sqcup q_2 0 0 0 \vdash \sqcup \text{x} q_3 0 0 \vdash \sqcup \text{x} 0 q_4 0 \\\\ &\vdash \sqcup \text{x} 0 \text{x} q_3 \sqcup \vdash \sqcup \text{x} 0 q_5 \text{x} \sqcup \vdash \sqcup \text{x} q_5 0 \text{x} \sqcup \\\\ &\vdash \sqcup q_5 \text{x} 0 \text{x} \sqcup \vdash q_5 \sqcup \text{x} 0 \text{x} \sqcup \vdash \sqcup q_2 \text{x} 0 \text{x} \sqcup \\\\ &\vdash \sqcup \text{x} q_2 0 \text{x} \sqcup \vdash \sqcup \text{x} \text{x} q_3 \text{x} \sqcup \vdash \sqcup \text{x} \text{x} \text{x} q_3 \sqcup \\\\ &\vdash \sqcup \text{x} \text{x} q_5 \text{x} \sqcup \vdash \sqcup \text{x} q_5 \text{x} \text{x} \sqcup \vdash \sqcup q_5 \text{x} \text{x} \text{x} \sqcup \\\\ &\vdash q_5 \sqcup \text{x} \text{x} \text{x} \sqcup \vdash \sqcup q_2 \text{x} \text{x} \text{x} \sqcup \vdash \sqcup \text{x} q_2 \text{x} \text{x} \sqcup \\\\ &\vdash \sqcup \text{x} \text{x} q_2 \text{x} \sqcup \vdash \sqcup \text{x} \text{x} \text{x} q_2 \sqcup \vdash \sqcup \text{x} \text{x} \text{x} \sqcup q_{\mathrm{accept}}. \end{align*} \]

Proof sketch.

Given a \(k\)-tape Turing machine \(M\), we construct a single-tape machine \(S\) that simulates \(M\). The single tape of \(S\) represents the contents of all \(k\) tapes of \(M\) by storing them consecutively, separated by a fresh delimiter symbol \(\#\): \[ \# \, \text{tape}_1 \, \# \, \text{tape}_2 \, \# \, \cdots \, \# \, \text{tape}_k \, \#. \] To track each head's position, \(S\) marks the cell where \(M\)'s head currently sits on each tape with a "dotted" version of that symbol (a new symbol added to the tape alphabet). For instance, if \(M\)'s tape \(i\) contains \(010\) with the head on the middle \(1\), \(S\) records \(\#0\dot{1}0\#\).

On input \(w\), \(S\) first formats its tape into this representation (with \(w\) on tape 1 and the remaining tapes blank). To simulate one step of \(M\), \(S\) scans across its tape from the leftmost \(\#\) to the \((k+1)\)-st \(\#\) to read the symbols under all virtual heads, then makes a second pass to update the contents and head positions according to \(M\)'s transition function. If a virtual head moves rightward onto a delimiter \(\#\), \(S\) shifts the tape contents to the right of that delimiter one cell further right, opening up a fresh blank cell for the head to occupy. \(S\) accepts (or rejects) precisely when \(M\) does. Hence \(S\) recognizes the same language as \(M\). \(\blacksquare\)

Proof Sketch.

We sketch each claim in turn.

Claim 1 (every CFL is decidable). Given a CFL \(L\) generated by a context-free grammar \(G\), the membership question "is \(w \in L\)?" can be decided by the Cocke–Younger–Kasami (CYK) algorithm: assuming \(G\) has been pre-converted into Chomsky Normal Form (a static, design-time transformation, not part of the input-processing), the algorithm uses dynamic programming to build up the set of variables that can derive each substring of \(w\) and accepts iff the start variable derives \(w\) itself. The procedure halts on every input in time \(O(|w|^3)\), so the Turing machine implementing it decides \(L\).

Claim 2 (some Turing-recognizable languages are undecidable). The canonical example is the acceptance problem \[ A_{\mathrm{TM}} = \{ \langle M, w \rangle \mid M \text{ is a Turing machine that accepts } w \}. \] \(A_{\mathrm{TM}}\) is Turing-recognizable: a universal Turing machine takes \(\langle M, w \rangle\) as input, simulates \(M\) on \(w\), and accepts whenever \(M\) accepts. However \(A_{\mathrm{TM}}\) is undecidable. The proof, classically due to Turing, uses a diagonalization argument analogous to the one we develop in the next section: assuming a decider for \(A_{\mathrm{TM}}\) exists, one constructs a Turing machine that contradicts itself when run on its own description.

Claim 3 (decidable iff Turing-recognizable and co-Turing-recognizable). (\(\Rightarrow\)) If \(L\) is decidable, a decider \(M\) for \(L\) recognizes \(L\) (so \(L\) is Turing-recognizable); swapping \(q_{\mathrm{accept}}\) and \(q_{\mathrm{reject}}\) in \(M\) yields a decider, hence recognizer, for \(L^c\). (\(\Leftarrow\)) Suppose \(M_1\) recognizes \(L\) and \(M_2\) recognizes \(L^c\). Build a new Turing machine \(M\) that, on input \(w\), simulates \(M_1\) and \(M_2\) in parallel step by step (advancing each machine by one step in alternation, on a shared input). Since every \(w\) lies in exactly one of \(L\) or \(L^c\), exactly one of \(M_1, M_2\) eventually accepts; \(M\) halts and accepts (resp. rejects) when \(M_1\) (resp. \(M_2\)) accepts. Thus \(M\) decides \(L\). \(\blacksquare\)

Proof.

Suppose for contradiction that \(f: X \to \mathcal{P}(X)\) is a bijection. Define the set \[ D = \{ x \in X \mid x \notin f(x) \} \in \mathcal{P}(X). \] Since \(f\) is surjective, there exists \(d \in X\) with \(f(d) = D\). Now ask: is \(d \in D\)?

• If \(d \in D\), then by definition of \(D\) we have \(d \notin f(d) = D\) — contradiction.
• If \(d \notin D\), then by definition of \(D\) we have \(d \in f(d) = D\) — contradiction.

Either case is contradictory, so no such bijection \(f\) exists. Taking \(X = \mathbb{N}\) gives \(\mathcal{P}(\mathbb{N})\) uncountable, since by definition a set is countable if and only if it is in bijection with \(\mathbb{N}\) (or a subset thereof). \(\blacksquare\)

Proof.

First, we show that the set of all Turing machines is countable. Each Turing machine \(M\) can be encoded as a finite string \(\langle M \rangle\) over some fixed alphabet \(\Sigma\) — for instance, by serializing its 7-tuple specification with appropriate delimiters, in such a way that distinct machines produce distinct strings (i.e., the encoding is injective). The set of all strings \(\Sigma^*\) over the alphabet \(\Sigma\) can be written as \[ \Sigma^* = \bigcup_{n \geq 0} \Sigma^n, \] where \(n\) is any nonnegative integer, and \(\Sigma^n\) is the set of strings of length \(n\). Since each \(\Sigma^n\) is finite and a countable union of finite sets is countable, it follows that \(\Sigma^*\) is countable. The encoding \(M \mapsto \langle M \rangle\) is injective, so the set of all Turing machines is in bijection with a subset of \(\Sigma^*\), and hence is also countable.

Next, we show that the set of all languages over \(\Sigma\) is uncountable. A language over \(\Sigma\) is, by definition, any subset of \(\Sigma^*\), so the set of all languages is exactly \(\mathcal{P}(\Sigma^*)\). Since \(\Sigma^*\) is countably infinite, it is in bijection with \(\mathbb{N}\); transporting Cantor's theorem (above) along this bijection gives that \(\mathcal{P}(\Sigma^*)\) is uncountable.

Therefore, since the set of all Turing machines is countable and the set of all languages is uncountable, there exist languages that cannot be recognized by any Turing machine. \(\blacksquare\)