16.1 Turing Machines

A Turing machine is a deliberately small mathematical model of computation. It has no parser, heap, operating system, or hardware pipeline. It has an unbounded tape divided into cells, a finite alphabet, a read/write head, and a finite control state. Despite this simplicity, it can express every algorithm that ordinary programmable computers can express, given enough time and tape. That makes it useful for discussing what computation can achieve in principle, independently of engineering speed.

A deterministic single-tape machine is commonly written as a tuple

M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)

Q is a finite set of states. Σ is the input alphabet and excludes the blank symbol. Γ is the tape alphabet and contains Σ plus blank and any working markers. The transition function δ maps a non-halting state and scanned symbol to a new state, symbol to write, and head movement L or R. The start, accept, and reject states have distinguished roles.

A configuration captures one instant of computation

A machine's complete instantaneous state is a configuration: current control state, nonblank tape contents, and head position. One transition changes exactly that configuration. Consider unary increment, where input 111 represents three:

δ(scan, 1) = (scan, 1, R)
δ(scan, □) = (accept, 1, R)

111□  →  111□  →  111□  →  1111
 ^          ^          ^          ^

The head scans right over every 1, then replaces the first blank with 1. Binary increment is slightly richer: start on the least-significant bit, replace trailing 1s with 0s while carrying left, and replace the first 0 or left blank with 1.

An input is accepted if the machine reaches q_accept, rejected if it reaches q_reject, and divergent if it continues forever. Divergence is not the same as rejection unless the machine is specifically a decider that halts on every input. A transition table may be partial; an undefined transition must have an explicitly stated meaning, usually reject or stuck, rather than being silently guessed.

Programs and inputs can both be encoded as data

A Turing machine has finitely many states and transition rules, so its description can be encoded as a finite string. Assign numbers to states and tape symbols, encode each transition tuple, and use a self-delimiting scheme so records and the machine/input boundary are recoverable. We can then write ⟨M,w⟩ for an encoding of machine M together with input w.

A universal Turing machine U reads ⟨M,w⟩ and simulates M on w. The simulated program is data on U's tape, just as bytecode is data to the virtual machines in Chapter 15. This is the mathematical core of stored-program computing, interpreters, emulators, and metacircular tools. It also enables self-reference: a program description can be supplied as its own input.

Variants change efficiency, not computability

Multi-tape machines, nondeterministic machines, machines with two-way infinite tapes, register machines, lambda calculus, and general-purpose programming languages all compute the same class of partial functions under standard effectiveness assumptions. A multi-tape machine may solve a task far more conveniently, but a single-tape machine can simulate it with overhead. This distinction separates computability—whether any algorithm exists—from complexity—how many resources an algorithm needs.

Turing machines are not proposed as practical compiler IR. Their value is abstraction. If a compiler pass or analyzer can be implemented as an ordinary terminating program, it can be modeled by a Turing machine. If a decision problem is proved impossible for Turing machines, adding a faster CPU, more threads, LLVM, a JIT, or a richer implementation language cannot create a general algorithm for it.

The model still assumes unbounded potential storage. Any particular physical computer has finite memory and therefore finitely many configurations, but that observation does not solve arbitrary program questions in a useful general model: the bound changes with the machine and may be astronomically large, and production languages model allocations and inputs without one fixed global cap. The coming sections use encoded machines, simulation, and self-reference to draw exact boundaries around decidability and static analysis.