The Universal Turing Machine

Contents

Coding a machine as a string
Extra tapes buy no extra power
Construction of $U$

This appendix proves Theorem 7.95 of Logic, Sets, and Maps: there is a single Turing machine $U$ which, given the code of any machine $M$ together with an input $w$, reproduces exactly what $M$ does on $w$. The theorem is the reason a computer is a general-purpose device rather than a machine built for one task, and it is the technical core of [Turing:1937]. It is also what makes Theorem 7.96 possible: a machine that can run any machine can be asked to run itself.

The machine of Definition 7.92 has one tape. Building $U$ directly in that format is possible but obscures the argument in bookkeeping, so we proceed in two steps: first show that extra tapes buy no extra power (Lemma A6.2), then construct $U$ with three of them.

Coding a machine as a string

Fix a machine $M=(Q,\Gamma,\sqcup,\Sigma,\delta,q_{0})$. Number its states $q_{0},q_{1},\ldots,q_{r}$ and its tape symbols $a_{0}=\sqcup,a_{1},\ldots,a_{s}$, and write $\mathrm{bin}(i)$ for the binary numeral of $i$. Each transition $\delta(q_{i},a_{j})=(q_{k},a_{l},D)$ is coded by the block

\begin{equation} \tag{A6.1} \mathrm{bin}(i)\,,\,\mathrm{bin}(j)\,,\, \mathrm{bin}(k)\,,\,\mathrm{bin}(l)\,,\,d\ec \qquad d\in\set{L,R}\ec \end{equation}

and the code of the whole machine is the concatenation of the blocks for all pairs on which $\delta$ is defined, separated by the marker ; and enclosed by \#:

\begin{equation} \tag{A6.2} \ulcorner M\urcorner:= \#\,B_{1}\,;\,B_{2}\,;\cdots;\, B_{m}\,\#\ep \end{equation}

The alphabet of the code is the fixed finite set $\set{0,1,,,;,\#, L,R}$, the same for every $M$ however large $Q$ and $\Gamma$ are — which is what allows one machine $U$, with one fixed alphabet, to read them all.

Two properties are immediate from Equation (A6.2) and are used below. First, whether a string is a well-formed code is decidable in the sense of Definition 7.93: a machine scans left to right and checks that the punctuation alternates as the format requires and that every block has five fields. Second, a machine can look up a transition: given $\mathrm{bin}(i)$ and $\mathrm{bin}(j)$ written somewhere on its tape, it walks the blocks in order, comparing the first two fields of each with the target pair symbol by symbol, and either finds the matching block or reaches the closing \#. Both are bounded searches through a finite string.

Extra tapes buy no extra power

Definition A6.1 ($k$-tape machine).

A $k$-tape Turing machine has $k$ two-way unbounded tapes with independent heads, and a transition function

\begin{equation} \tag{A6.3} \delta:Q\times\Gamma^{k}\longrightarrow Q\times\Gamma^{k}\times\set{L,R,S}^{k}\ec \end{equation}

reading the $k$ scanned symbols at once and writing, and moving each head left, right or not at all. Input is on tape 1, output read from tape 1; undefined $\delta$ means halt. Rests on Definition 7.92.

Lemma A6.2 (Tape reduction).

For every $k$-tape machine $N$ there is a single-tape machine $N'$, in the sense of Definition 7.92, computing the same partial function. If $N$ halts on $w$ in $n$ steps, $N'$ halts on $w$ in $O(n^{2})$ steps. Rests on Definitions 7.92 and A6.1.

Proof.

Derives Lemma A6.2. The construction is to lay the $k$ tapes out as $2k$ parallel tracks of one tape. A tape whose cells each carry a $2k$-tuple of symbols is nothing more than a tape over the alphabet

\begin{equation} \tag{A6.4} \Gamma':=\left(\Gamma\cup\set{\sqcup}\right)^{k}\times \set{0,1}^{k}\ec \end{equation}

which is a finite set — it has $(\abs{\Gamma})^{k}2^{k}$ elements — so $N'$ is a legitimate single-tape machine over a legitimate finite alphabet. Of each pair of tracks, the first holds the contents of simulated tape $i$ and the second holds a single $1$ marking where head $i$ stands, all other cells of that track carrying $0$.

$N'$ keeps the simulated state of $N$ in its own finite control, which is possible because $Q$ is finite. One simulated step is performed by two sweeps.

Gathering sweep. $N'$ walks right from the left end of the used region to its right end, remembering in its control which of the $k$ head markers it has passed and which symbol stood beneath each. There are $k$ markers and each carries one of $\abs{\Gamma}$ symbols, so the information to be remembered is one of $(\abs{\Gamma})^{k}$ possibilities — a finite number, hence storable in the control. At the end of the sweep $N'$ knows the full $k$-tuple of scanned symbols, which is exactly the argument $\delta$ of Equation (A6.3) requires.

Writing sweep. $N'$ consults $\delta$ — a fixed finite table built into its control — obtaining the new state, the $k$ symbols to write and the $k$ head movements. It then walks back left, and at each marker it passes it writes the new symbol on that track and moves the marker one cell left, right, or not at all as prescribed. It records the new state in its control. If $\delta$ was undefined on the tuple, $N'$ halts instead.

The used region grows by at most one cell per simulated step in each direction, so after $n$ simulated steps it has length $O(n)$ and each sweep costs $O(n)$ moves; $n$ simulated steps therefore cost $O(n^{2})$ moves of $N'$. Finally, the input arrives on a single ordinary tape, so $N'$ begins with a preparatory pass converting it to the track format, and ends with one converting track 1 back; each is $O(n)$.

By construction the track contents after the $n$-th simulated step encode the tapes of $N$ after its $n$-th step, and $N'$ halts exactly when $N$ does, so the two compute the same partial function.

∎

Construction of $U$

Theorem A6.3.

There is a Turing machine $U$ such that for every machine $M$ and every input $w$, $U$ on input $(\ulcorner M\urcorner,w)$ halts if and only if $M$ halts on $w$, and then leaves the same output. Rests on Equation (A6.2), Lemma A6.2 and Definition 7.92.

Proof.

Derives Theorem A6.3. We build $U$ with three tapes and appeal to Lemma A6.2 at the end.

Layout. Tape 1 holds $\ulcorner M\urcorner$ and is never altered. Tape 2 holds the simulated tape of $M$, with each symbol $a_{j}$ of $\Gamma$ represented by the block $\mathrm{bin}(j)$ and blocks separated by ,; the simulated head position is marked by a dot on the first symbol of one block, which costs only a doubling of the tape alphabet. Tape 3 holds $\mathrm{bin}(i)$ for the current simulated state $q_{i}$.

Initialization. $U$ first verifies that tape 1 carries a well-formed code, as described in Coding a machine as a string, and halts rejecting if not. It then converts the input $w=w_{1}\cdots w_{p}$ into block form on tape 2, marks the first block, and writes $\mathrm{bin}(0)$ on tape 3. Tape 2 now encodes the initial configuration of $M$ on $w$.

The step loop. $U$ repeats the following.

Read the marked block on tape 2 into the control — it is $\mathrm{bin}(j)$ for the currently scanned symbol $a_{j}$ — and read $\mathrm{bin}(i)$ from tape 3. Neither can be held in the finite control as a whole, since $\abs{Q}$ and $\abs{\Gamma}$ are unbounded across machines $M$; instead $U$ keeps its head positions and compares symbol by symbol, which is why the lookup is a scan rather than a table jump.
Walk tape 1 from the left \#, comparing the first two fields of each block with $\mathrm{bin}(i)$ and $\mathrm{bin}(j)$. Comparison is performed by moving the two heads in step and matching one binary digit at a time.
If the closing \# is reached with no match, then $\delta$ is undefined at $(q_{i},a_{j})$; $U$ erases its scaffolding, converts tape 2 back to plain symbols, copies it to the output tape and halts.
If a block matches, read its remaining three fields $\mathrm{bin}(k)$, $\mathrm{bin}(l)$, $d$. Copy $\mathrm{bin}(k)$ over tape 3. Overwrite the marked block of tape 2 with $\mathrm{bin}(l)$, shifting the rest of the tape if the two blocks differ in length. Move the mark to the neighbouring block in the direction $d$, appending a fresh block $\mathrm{bin}(0)$ for $\sqcup$ if the mark would leave the written region.

Faithfulness. We claim that for every $n$, if $M$ has not halted within $n$ steps then after $n$ passes through the loop, tape 2 encodes the tape of $M$ after $n$ steps with the mark on the scanned cell, and tape 3 holds the numeral of $M$'s state after $n$ steps. The proof is induction on $n$ (Axiom 7.34).

For $n=0$ this is what initialization established. Assume it for $n$. Then at step 1 of pass $n+1$, $U$ reads exactly the state $q_{i}$ and scanned symbol $a_{j}$ that $M$ has after $n$ steps. Step 2 locates the block Equation (A6.1) for that pair, and by Equation (A6.2) there is at most one such block, since $\delta$ is a function. If none exists, $M$ halts at step $n+1$ by Definition 7.92, and step 3 makes $U$ halt with tape 2 decoding to $M$'s final tape. If one exists, step 4 writes $a_{l}$ in place of $a_{j}$, moves the mark one cell in the direction $D$ and records $q_{k}$ — which is precisely the action Definition 7.92 prescribes for step $n+1$. So the claim holds for $n+1$.

Consequently $U$ performs a pass for each step of $M$ and halts exactly when $M$ halts, with the same output; and if $M$ never halts, neither branch of step 3 is ever taken and $U$ loops forever as well. Finally, Lemma A6.2 converts this three-tape $U$ into a single-tape machine with the same behaviour, which is the machine promised by Theorem 7.95.

∎

Remark A6.4 (What the construction costs).

Each pass of the loop scans a code of fixed length $\abs{\ulcorner M\urcorner}$ and a simulated tape of length $O(n)$ after $n$ steps, so $U$ simulates $n$ steps of $M$ in $O(n^{2}\abs{\ulcorner M\urcorner})$ of its own, and the reduction to one tape squares that again. The overhead is polynomial, and that is the point: universality costs a slowdown, never a loss of what can be computed at all. This is the precise sense in which Axiom 7.94 is unaffected by the choice of machine model.

The Universal Turing Machine discharges the proof obligation of Theorem 7.95. Its consequence is the one exploited throughout Section 7.9: a program is a string, a string is data, and data can be fed to a program — including to the program that produced it. Theorem 7.96 is that observation turned against itself, and Theorem 7.97 generalizes the damage.