Turing machines

Turing’s 1936 model arises from an analysis of a human computing with pencil and paper. The paper is replaced by a one-dimensional tape divided into cells, each holding one symbol from a finite alphabet. The person’s attention is a head scanning one cell at a time. Their state of mind, which can only take finitely many values, is the state of the machine. At each step, the action depends only on the current state and on the scanned symbol, and consists in writing a symbol, moving one cell left or right, and changing state.

2.1 Definition

Definition 2.1.#

A Turing machine is a tuple $M = (Q, \Gamma, \delta, q_0, q_h)$ where

• $Q$ is a finite set of states, with an initial state $q_0 \in Q$ and a halting state $q_h \in Q$, $q_h \neq q_0$;
• $\Gamma$ is a finite alphabet containing at least the blank symbol $\sqcup$ and the symbol $1$;
• $\delta : (Q \setminus \{q_h\}) \times \Gamma \to Q \times \Gamma \times \{L, R\}$ is the transition function.

An entry $\delta(q, a) = (q', b, D)$ reads: in state $q$, scanning $a$, write $b$, move in direction $D$, and enter state $q'$. Since $\delta$ is defined on all pairs $(q, a)$ with $q \neq q_h$, the machine can always perform a step unless it is in the halting state. A machine is a finite object: it can be written as a finite table, and there are only countably many machines (up to renaming of states and symbols).

To describe the state of a computation, we index the cells of the tape by $\mathbb{Z}$.

Definition 2.2.#

A tape is a function $\tau : \mathbb{Z} \to \Gamma$ such that $\tau(i) = \sqcup$ for all but finitely many $i$. A configuration of $M$ is a triple $C = (q, \tau, h)$ where $q \in Q$, $\tau$ is a tape and $h \in \mathbb{Z}$ is the head position. The configuration is halting if $q = q_h$.

If $C = (q, \tau, h)$ is not halting and $\delta(q, \tau(h)) = (q', b, D)$, the successor of $C$ is the configuration $C' = (q', \tau', h')$ where

$$\tau'(i) = \begin{cases} b & \text{if } i = h, \\ \tau(i) & \text{otherwise,} \end{cases} \qquad h' = \begin{cases} h - 1 & \text{if } D = L, \\ h + 1 & \text{if } D = R. \end{cases}$$

We write $C \vdash_M C'$, or simply $C \vdash C'$.

Every non-halting configuration has exactly one successor, and a halting configuration has none: Turing machines are deterministic.

Definition 2.3.#

The computation of $M$ from a configuration $C_0$ is the sequence $C_0 \vdash C_1 \vdash C_2 \vdash \cdots$, which is either infinite, or finite and ends with the first halting configuration $C_t$. In the second case we say that $M$ halts from $C_0$ after $t$ steps, with final configuration $C_t$.

2.2 Computing functions

To compute functions on integers we fix conventions for representing inputs and outputs on the tape. We use unary notation, representing $x \in \nat$ by $x + 1$ consecutive $1$s:

$$\ulcorner x \urcorner = 1^{x+1}.$$

Using $x+1$ rather than $x$ symbols ensures that every number, including $0$, occupies at least one cell, so that a tuple of numbers separated by single blanks can be read unambiguously.

Definition 2.4.#

Let $M$ be a Turing machine and $k \geq 1$.

• The initial configuration on input $\vec x = (x_1, \dots, x_k)$ is $(q_0, \tau_{\vec x}, 0)$, where the tape $\tau_{\vec x}$ contains the word $\ulcorner x_1 \urcorner \sqcup \ulcorner x_2 \urcorner \sqcup \cdots \sqcup \ulcorner x_k \urcorner$ written from cell $0$ onwards, and blanks elsewhere.
• A configuration $(q_h, \tau, h)$ is a standard final configuration with output $y$ if $\tau(i) = 1$ for $h \leq i \leq h + y$ and $\tau(i) = \sqcup$ for all other $i$: the tape contains exactly $\ulcorner y \urcorner$, and the head scans its first cell.

The partial function $\varphi^{(k)}_M : \nat^k \rightharpoonup \nat$ computed by $M$ is defined by: $\varphi^{(k)}_M(\vec x)\converge = y$ if the computation of $M$ from the initial configuration on input $\vec x$ halts in a standard final configuration with output $y$, and $\varphi^{(k)}_M(\vec x)\diverge$ otherwise.

A partial function $f : \nat^k \rightharpoonup \nat$ is Turing-computable if $f = \varphi^{(k)}_M$ for some machine $M$.

Note that $\varphi^{(k)}_M(\vec x)$ is undefined both when the computation does not halt and when it halts in a non-standard configuration. With this convention every machine computes exactly one $k$-ary partial function, for each $k$.

Remark 2.5.

The precise conventions — unary or binary notation, a tape infinite in one or both directions, a cleaned tape at the end or not — vary between textbooks. They change the machines, but not the class of Turing-computable functions. The robustness of the class under such changes is discussed in the next lesson.

2.3 First example: the successor function

Let $M_S$ be the machine with states $\{q_0, q_1, q_h\}$, alphabet $\{\sqcup, 1\}$, and transitions

	$1$	$\sqcup$
$q_0$	$(q_0, 1, R)$	$(q_1, 1, L)$
$q_1$	$(q_1, 1, L)$	$(q_h, \sqcup, R)$

In state $q_0$ the head runs right across the input. On the first blank it writes a $1$ and turns back in state $q_1$, runs left to the blank preceding the block, and steps back onto the first $1$.

Proposition 2.6.#

$M_S$ computes the successor function: $\varphi^{(1)}_{M_S}(x) = x + 1$ for every $x$.

Proof of Proposition 2.6.

Write $\tau_n$ for the tape containing $1$s exactly on the cells $0, \dots, n$. The initial configuration on input $x$ is $(q_0, \tau_x, 0)$. For $i \leq x$, the cell $i$ contains $1$, so by the first transition

$$(q_0, \tau_x, 0) \vdash (q_0, \tau_x, 1) \vdash \cdots \vdash (q_0, \tau_x, x+1).$$

Cell $x+1$ is blank, so the next configuration is $(q_1, \tau_{x+1}, x)$. For $0 \leq i \leq x$ the cell $i$ contains $1$, so

$$(q_1, \tau_{x+1}, x) \vdash (q_1, \tau_{x+1}, x - 1) \vdash \cdots \vdash (q_1, \tau_{x+1}, -1).$$

Cell $-1$ is blank, so the next configuration is $(q_h, \tau_{x+1}, 0)$. This is a standard final configuration with output $x + 1$, reached after $2x + 4$ steps.

The proof follows a pattern used for all such verifications: describe the configurations at the beginning and at the end of each phase of the computation, and check each phase by induction on the number of steps.

2.4 Second example: addition

The machine $M_+$ below computes $(x, y) \mapsto x + y$. On input $\ulcorner x \urcorner \sqcup \ulcorner y \urcorner$, it replaces the separating blank by a $1$, which produces a block of $x + y + 3$ ones; it then erases the last two $1$s and returns to the beginning of the block.

	$1$	$\sqcup$
$q_0$	$(q_0, 1, R)$	$(q_1, 1, R)$
$q_1$	$(q_1, 1, R)$	$(q_2, \sqcup, L)$
$q_2$	$(q_3, \sqcup, L)$	$(q_h, \sqcup, R)$
$q_3$	$(q_4, \sqcup, L)$	$(q_h, \sqcup, R)$
$q_4$	$(q_4, 1, L)$	$(q_h, \sqcup, R)$

The entries $\delta(q_2, \sqcup)$ and $\delta(q_3, \sqcup)$ are never used on inputs of the required form; they are only there to make $\delta$ total.

Proposition 2.7.#

$M_+$ computes addition: $\varphi^{(2)}_{M_+}(x, y) = x + y$ for all $x, y$.

Proof of Proposition 2.7.

The initial tape has $1$s on the cells $0, \dots, x$ and $x + 2, \dots, x + y + 2$, and a blank on cell $x + 1$. In state $q_0$ the head moves right to cell $x + 1$, writes $1$ there and moves to cell $x + 2$ in state $q_1$. Now the tape contains $1$s exactly on $0, \dots, x + y + 2$. In state $q_1$ the head moves right to cell $x + y + 3$, which is blank, and moves back to cell $x + y + 2$ in state $q_2$. It erases this cell and moves to cell $x + y + 1$ in state $q_3$. Since $0 \leq x + y + 1 < x + y + 2$, this cell belongs to the block written in the first phase and has not been erased, so it contains $1$; it is erased and the head moves to cell $x + y$ in state $q_4$. The tape now contains $1$s exactly on $0, \dots, x + y$. As in the previous proof, $q_4$ runs left to cell $-1$, and the machine halts with the head on cell $0$. The final configuration is standard with output $x + y$.

2.5 Exercises

Exercise 2.8 ★.

Give a machine computing the constant function $x \mapsto 0$, and prove that it is correct.

Solution

The machine must erase all $1$s but the first and return to cell $0$:

	$1$	$\sqcup$
$q_0$	$(q_1, 1, R)$	$(q_h, \sqcup, R)$
$q_1$	$(q_1, \sqcup, R)$	$(q_2, \sqcup, L)$
$q_2$	$(q_3, 1, L)$	$(q_2, \sqcup, L)$
$q_3$	$(q_h, 1, R)$	$(q_h, \sqcup, R)$

On input $x$ the head steps from cell $0$ to cell $1$ in state $q_1$, erases cells $1, \dots, x$ and reaches the blank cell $x + 1$, moves back to cell $x$ in state $q_2$, moves left over the blanks $x, \dots, 1$ to cell $0$, which contains $1$, moves to cell $-1$ in state $q_3$, and finally halts on cell $0$. The tape contains a single $1$ on cell $0$: the output is $0$. The entries $\delta(q_0, \sqcup)$ and $\delta(q_3, 1)$ are never used.

Exercise 2.9 ★.

Give a machine computing the projection $(x, y) \mapsto x$.

Solution

Run right to the separator, step over it, erase the block $\ulcorner y \urcorner$ until reaching the blank after it, then run left over blanks until the last $1$ of $\ulcorner x \urcorner$, then left over the $1$s to cell $-1$, and step right:

	$1$	$\sqcup$
$q_0$	$(q_0, 1, R)$	$(q_1, \sqcup, R)$
$q_1$	$(q_1, \sqcup, R)$	$(q_2, \sqcup, L)$
$q_2$	$(q_3, 1, L)$	$(q_2, \sqcup, L)$
$q_3$	$(q_3, 1, L)$	$(q_h, \sqcup, R)$

In state $q_2$, the head moves left over the erased cells and the separator until it reaches cell $x$, the last $1$ of the first block.

Exercise 2.10 ★.

Show that every Turing-computable partial function is computed by infinitely many machines. Show that there are only countably many Turing-computable partial functions $\nat \rightharpoonup \nat$, and deduce that there is a total function $\nat \to \nat$ which is not Turing-computable.

Solution

Adding to a machine states that are never entered does not change its computations, so each computable function has infinitely many machines. Up to renaming, a machine is determined by finitely many data — the numbers of states and symbols, and the table of $\delta$ — so it can be described by a finite string over a finite alphabet, and there are countably many machines; hence countably many computable functions. The set of total functions $\nat \to \nat$ is uncountable (by a diagonal argument, see The diagonal argument), so some total function is not computable.

2.6 Notes and references

Turing’s machines (1936) differ from ours in inessential details: they compute infinite binary sequences rather than functions, and halting plays no role. Post introduced an almost identical model independently in the same year. The representation of $x$ by $x + 1$ strokes is that of Kleene (Introduction to Metamathematics, §67); the requirement of a standard final configuration, with the output alone on the tape and the head on its first cell, is close to the conventions of Boolos, Burgess and Jeffrey.

• E. L. Post, Finite combinatory processes — formulation 1, Journal of Symbolic Logic 1 (1936), 103–105.
• S. C. Kleene, Introduction to Metamathematics, North-Holland, 1952.
• G. Boolos, J. Burgess, R. Jeffrey, Computability and Logic, 5th edition, Cambridge University Press, 2007.