Turing Machine

A Turing machine is what is left of a computer when you remove everything you can remove and still compute every computable function.

Formal definition

A Turing machine is a 7-tuple

where

• $Q$ is a finite set of states;
• $\Sigma$ is a finite set, the input alphabet, with $\sqcup \notin \Sigma$;
• $\Gamma$ is a finite set, the tape alphabet, with $\Sigma \subseteq \Gamma$ and $\sqcup \in \Gamma$;
• $\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ is the transition function;
• $q_0 \in Q$ is the initial state;
• $q_{\text{accept}}, q_{\text{reject}} \in Q$ are the accept and reject states, with $q_{\text{accept}} \neq q_{\text{reject}}$.

The computation halts upon entering $q_{\text{accept}}$ or $q_{\text{reject}}$, and $\delta$ is never consulted in either state. The symbol $\sqcup$ is the blank.

Configurations. A configuration of $M$ is a string $u\,q\,v \in \Gamma^* \cdot Q \cdot \Gamma^*$, interpreted as follows: the tape contents, read from the leftmost cell rightward, are $uv$ followed by infinitely many blanks; the current state is $q$; the head is on the first symbol of $v$, or on the leftmost blank if $v = \varepsilon$. The initial configuration of $M$ on input $w \in \Sigma^*$ is $q_0\,w$.

Computation step. The one-step relation $\vdash_M$ on configurations is the smallest binary relation satisfying: whenever $\delta(q, a) = (q', b, R)$,

and symmetrically for $L$-moves, with the convention that the head stays in place when attempting to move off the left end of the tape. The reflexive–transitive closure is written $\vdash_M^*$.

Language recognized. The language recognized by $M$ is

On a given input $w$, exactly one of three things happens: $M$ halts in $q_{\text{accept}}$ (accepts), halts in $q_{\text{reject}}$ (rejects), or never halts (loops). A language $L \subseteq \Sigma^*$ is Turing-recognizable (or recursively enumerable) if $L = L(M)$ for some Turing machine $M$. It is Turing-decidable (or recursive) if some Turing machine recognizes $L$ and halts on every input. Every decidable language is recognizable; the halting problem witnesses that the converse fails.

Intuition

The whole machinery sits inside one function. Fix a finite set of states $Q$, a finite tape alphabet $\Gamma$, and a transition function $\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$. At every step the machine looks at the single symbol under its head, consults $\delta$, writes a symbol, moves one cell, and enters a new state. That is the entire program. Nothing else ever happens.

This is almost offensively little, and the surprise is that it is enough. The tape supplies unbounded memory; the states supply finite control. Every program a laptop runs — text editor, compiler, proof checker, physics simulator — reduces to a sequence of such triples. The reducibility is not a metaphor. It is a construction: lambda calculus, register machines, and general recursive functions all compile down to transition functions of this shape.

Read $\delta$ carefully. Its domain is state × current symbol, never a window of context, never a history of what was just read. Whatever memory the machine needs must live on the tape, and the head must walk there to consult it. The model is deliberately stingy about what the present moment can see. This parsimony is the whole point: a computational step should depend on nothing except a finite piece of information locally available to the machine. Anything more permissive lets the definition cheat; anything less leaves it inert.

Notice what a Turing machine does not model. The cost of a single step is not calibrated to anything physical: one transition might correspond to a nanosecond on a real chip or a month of pencil-and-paper work. There is no memory hierarchy — just one uniform tape, with nothing cached above it and nothing paged below. Parallelism is absent entirely. Readers arriving here from complexity theory or systems work should leave with the correct disillusionment: the Turing machine is a mathematical object about what can be computed. It has nothing to say about what computing feels like.

Examples

A Turing machine that decides $\{0^n 1^n : n \geq 0\}$. The machine repeatedly crosses off matching pairs. In each sweep it finds the leftmost unmarked $0$, replaces it with $X$, walks right to find the leftmost unmarked $1$, replaces it with $Y$, and walks back to start the next sweep. When the return walk finds no more unmarked $0$s, the machine verifies that the remaining tape contains only $Y$s followed by blanks, and accepts if so.

On input 0011, the configurations at the start of each step (the cell immediately to the right of a state label is the cell under the head) are:

q_0 0 0 1 1          initial
X q_1 0 1 1          δ(q_0, 0) = (q_1, X, R)
X 0 q_1 1 1          skip the remaining 0
X q_2 0 Y 1          δ(q_1, 1) = (q_2, Y, L)
q_2 X 0 Y 1          walk back across the 0
X q_0 0 Y 1          δ(q_2, X) = (q_0, X, R) — sweep 1 done
X X q_0 Y Y          end of sweep 2: no more 0s on the tape
X X Y q_3 Y          δ(q_0, Y) = (q_3, Y, R) — enter verify
X X Y Y q_3 ⊔        walked through the Y-block to the blank
X X Y Y ⊔ q_accept   accept

The tape has served as bounded memory — bounded by the input length in this run, though nothing in the definition forces that. The entire transition table fits in under twenty rows, and the machine uses four non-halting states: $q_0$ searches for the next unmarked $0$, $q_1$ walks right to find its matching $1$, $q_2$ walks back to the leftmost marker, and $q_3$ verifies the tail.

Notes

The Church–Turing thesis identifies the class of functions computable by a Turing machine with the informal notion of effective computability. Church’s $\lambda$-calculus, Gödel and Herbrand’s general recursive functions, Post’s tag systems, and Turing’s machine all compute the same class. The thesis is not a theorem: it equates a formal notion with an informal one and thus lives outside the reach of proof. Every serious attempt to extend the class in the past seventy years has either failed or collapsed back into it. The thesis, together with those failed extensions, deserves its own concept.

Turing’s original 1936 paper does not present the machine as a language recognizer. Its target is the Entscheidungsproblem — David Hilbert and Wilhelm Ackermann’s 1928 question of whether there exists a general procedure to decide the validity of any first-order sentence — and its main construction is a machine that prints the binary expansion of a computable real number. The language-theoretic reframing used above is the standard modern one, due in large part to the automata-theory textbooks of the 1960s. The two formulations are equivalent for decidability questions but live in different semantic homes: Turing’s paper is about computing numbers; ours is about recognizing sets.

Variants exist in profusion, and each deserves its own article. The non-deterministic Turing machine admits a transition relation rather than a function. The multi-tape Turing machine has $k$ tapes with independent heads. The universal Turing machine is a single machine that, given an encoding $\langle M, w \rangle$, simulates $M$ on $w$. The oracle Turing machine has access to a distinguished query tape consulting a fixed oracle. All are computationally equivalent to the single-tape deterministic model defined above, with at most polynomial slowdown for the first two.

A Turing machine is not a model of hardware. It has no registers, no clock, no arithmetic primitives, no memory hierarchy. Writing “a Turing machine is what a computer becomes in the limit of infinite memory” is lazy in the direction that matters: Turing machines are language recognizers, not simulators of machines. The engineering intuition is a pedagogical footnote; the formal object is the article.

Seventy years of hardware evolution have added registers, caches, parallelism, and quantum superposition. None of these has moved the boundary Turing drew in 1936. Subtract anything from his definition and it collapses; add anything and the addition is ornament.