2. Turing Machines
We saw in the last lecture that for every fixed machine, there exists a language that cannot be computed by algorithms for that specific machine. Our goal today is to strengthen this result to identify an explicit language that cannot be computed by algorithms over any machine model.
That is where Turing machines come in. The magic of this model of computation is that it satisfies what appear to be two contradictory goals. One, it is a very simple model. So simple that we will be able to analyze Turing machines directly and prove quite a few nontrivial statements about them. And two, it is general enough to capture what is computable by all other reaonable models of computation.
Definition of Turing Machines
The simplest Turing machine model is the deterministic 1-tape Turing machine.
This machine has two main components. There is the machine itself, which has a finite number of possible internal states. And there is an infinite tape split up into squares. Each square contains exactly one symbol. The machine has a tape head that is always positioned over one of the squares of the tape. At each step in the execution, the Turing machine uses its internal state and the symbol on the square of the tape under the tape head to determine its next action.
The action taken by a Turing machine at each computational step consists of three parts: the internal state it goes to, the symbol that is overwritten over the previous symbol on the square of tape under the tape head, and a movement Left or Right of the tape head to the square adjacent to the current one on the tape. In addition, the machine has two additional special actions that it can take to halt: one accepts, and the other rejects.
The input to a Turing machine is a string of binary symbols on the tape, surrounded by an infinite number of squares that contain a special blank symbol. We write \(\square\) to denote the special blank symbol. The tape head of the Turing machine is initially on the left-most symbol of the input. (In the special case where the input is the empty string \(\varepsilon\), the tape consists entirely of blank symbols and the tape head is over any one of them.)
The simplest way to define a Turing machine is via a transition diagram such as the following one.
The edges in the diagram describe all the actions that a Turing machine can do in a computational step. For example, the self-loop in the top right corner of the diagram above specifies that if the machine is currently in state \(\mathbf{3}\) and the tape head is over a square with the symbol \(1\), it writes a \(0\) on that square (overwriting the previous \(1\)), moves the tape head Left one square, and stays in state \(\mathbf{3}\).
We can also provide a formal definition of Turing machines in the following way.
Definition. A deterministic one-tape Turing machine is an abstract machine described by the triple
\[M = (m,k,\delta)\]with \(m,k \ge 1\) where
- \(\mathbf{Q} = \{\mathbf{1}, \mathbf{2}, \ldots, \mathbf{m}\}\) is the set of internal states,
- \(\Gamma = \{\square,0,1,2,\ldots,k\}\) is the tape alphabet, and
- \(\delta \colon \mathbf{Q} \times \Gamma \to (\mathbf{Q} \cup \{\mathbf{A}, \mathbf{R}\}) \times \Gamma \times \{L, R\}\) is the transition function.
The state \(\mathbf{1}\) denotes the initial state of the Turing machine \(M\). (We will use bold symbols to denote the states of the machine, to prevent any confusion with the symbols used on the tape.)
In order to simulate a Turing machine, we need to keep track of its internal state, the current string on the tape, and the position of the tape head on the tape. We call this information the configuration of a Turing machine. It can be represented conveniently in the following way.
Definition. The configuration of a Turing machine is a string \(w \mathbf{q} y\) where
- \(\mathbf{q} \in \mathbf{Q} \cup \{ \mathbf{A}, \mathbf{R} \}\) represents the current state of the machine,
- \(wy \in \Gamma^*\) is the current string on the tape, and
- the position of the tape head is on the first symbol of \(y\).
Two configurations are equivalent when they are identical up to blank symbols at the beginning of \(w\) or at the end of \(y\). In other words, they satisfy
\[w\mathbf{q}y = \square w \mathbf{q} y = w \mathbf{q} y \square.\]When \(\mathbf{q} = \mathbf{A}\), the string \(w \mathbf{q} y\) represents an accepting configuration. When \(\mathbf{q} = \mathbf{R}\), it represents a rejecting configuration. A configuration is a halting configuration if it is either accepting or rejecting.
A step of computation of a Turing machine typically changes its configuration. We can simulate a Turing machine by listing the configurations obtained after each computation step. For example, when running the Turing machine in the diagram above on the input \(1011\), the following sequence of configurations are obtained:
\[\begin{matrix} \mathbf{1} & 1 & & 0 & & 1 & & 1 & & \\ & 1 & \mathbf{2} & 0 & & 1 & & 1 & & \\ & 1 & & 0 & \mathbf{2} & 1 & & 1 & & \\ & 1 & & 0 & & 1 & \mathbf{2} & 1 & & \\ & 1 & & 0 & & 1 & & 1 & \mathbf{2} & \square \\ & 1 & & 0 & & 1 & \mathbf{3} & 1 & & \\ & 1 & & 0 & \mathbf{3} & 1 & & 0 & & \\ & 1 & \mathbf{3} & 0 & & 0 & & 0 & & \\ & 1 & & 1 & \mathbf{A} & 0 & & 0 & & \end{matrix}\]Note that the additional spacing in the representation of the configurations is not required by the definition, but it does make it easier to follow the simulation of the Turing machine. Note also that for clarity the blank squares on the tape are written explicitly only when they are required (as is the case in the step above where the tape head is positioned over a blank square).
A list of the configurations obtained during the execution of a Turing machine is called a tableau. We can also formally define which configurations follow each other in the execution of a Turing machine in the following way.
Definition. For any strings \(w,y \in \Gamma^*\), symbols \(a,b,c \in \Gamma\), and states \(\mathbf{q} \in \mathbf{Q}\) and \(\mathbf{r} \in \mathbf{Q} \cup \{ \mathbf{A}, \mathbf{R} \}\), the configuration \(wa\mathbf{q}by\) of the Turing machine \(M\) yields the configuration \(w \mathbf{r} acy\), denoted
\[wa \mathbf{q} by \vdash w \mathbf{r} acy\]when \(\delta(\mathbf{q},b) = (\mathbf{r},c,L)\). Similarly,
\[wa \mathbf{q} by \vdash wac \mathbf{r} y\]when \(\delta(\mathbf{q},b) = (\mathbf{r},c,R)\).
By simulating multiple steps of computation, a Turing machine can reach some other configurations. Specifically, we say that the configuration \(w \mathbf{q} y\) derives the configuration \(w' \mathbf{q'} y'\) in the Turing machine \(M\), denoted
\[w \mathbf{q} y \vdash^* w' \mathbf{q'} y'\]when there exists a finite sequence of configurations \(w_1 \mathbf{q}_1 y_1, \ldots, w_k \mathbf{q}_k y_k\) such that
\[w \mathbf{q} y \vdash w_1 \mathbf{q}_1 y_1 \vdash \cdots \vdash w_k \mathbf{q}_k y_k \vdash w' \mathbf{q'} y'.\]The Turing machine \(M\) accepts an input \(x \in \{0,1\}^*\) if the initial configuration \(\mathbf{1}x\) derives an accepting configuration. It rejects \(x\) if \(\mathbf{1}x\) derives a rejecting configuration. And it halts on \(x\) if and only if it either accepts or rejects \(x\).
With these definitions in place, we can now formally define what it means for a Turing machine to “compute” a language.
Definition. The Turing machine \(M\) decides the language \(L \subseteq \{0,1\}^*\) if it accepts every \(x \in L\) and rejects every \(x \notin L\).
A language is decidable if and only if there is a Turing machine that decides it. (The set of all decidable languages is also known as the set of recursive languages.)
There is a closely related notion of recognizability of languages.
Definition. The Turing machine \(M\) recognizes the language \(L \subseteq \{0,1\}^*\) if for every \(x \in \{0,1\}^*\), \(M\) accepts \(x\) if and only if \(x \in L\).
Note that in this definition of recognizability, the machine \(M\) can either reject or run forever on inputs \(x \notin L\). The set of recognizable languages is also known as the set of all recursively enumerable languages.
Every Turing machine recognizes a language. We write \(L(M)\) to denote the language recognized by \(M\). By contrast, not every Turing machine decides a language. The Turing machine \(M\) decides \(L(M)\) if and only if it rejects all the inputs in \(\{0,1\}^* \setminus L(M)\). Or, equivalently:
Proposition. The Turing machine \(M\) decides the language \(L(M)\) if and only if it halts on every input.