The Turing Machine Model

A Turing machine is a mathematical model consisting of a finite set of control states plus an infinite tape divided into cells, each holding one symbol from a finite tape alphabet. A read-write head sits over one tape cell at any moment; it can read the symbol there, overwrite it, and then move one cell left or one cell right. Unlike a finite automaton, whose input is consumed once, left to right, and never altered, a Turing machine can revisit and rewrite any cell it has already visited, and its tape extends without bound in at least one direction (conventionally to the right). The machine's behavior is governed by a single transition function `δ`, which, given the current state and the symbol currently under the head, deterministically specifies three things: the new state, the symbol to write, and the direction to move the head. Because `δ` is a function (not a relation), at most one applicable rule exists for any (state, symbol) pair — this is what makes the machine deterministic. Computation proceeds step by step from a designated start state, and halts only when the machine enters one of two special states: `q_accept` or `q_reject`. If neither is ever reached, the machine runs forever — this is a legitimate, and in fact theoretically crucial, third possible outcome of running a TM on an input, alongside "accept" and "reject." The tape alphabet `Γ` always contains the input alphabet `Σ` as a subset, together with a special blank symbol `␣ ∉ Σ`, which fills every tape cell that has not yet been written to. This is essential: it lets the machine detect "the edge of the meaningful input" and gives it working space beyond the input to write intermediate results, exactly the way scratch paper works for a human computing by hand. This tape-plus-blank mechanism is what allows a Turing machine to simulate any algorithm expressible in a real programming language, a claim formalized later as the Church-Turing Thesis.

The formal seven-tuple

A deterministic Turing machine is a 7-tuple ``` M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject) ``` where:

• Q — a finite set of states.
• Σ — the input alphabet, not containing the blank symbol `␣`.
• Γ — the tape alphabet, with `Σ ⊆ Γ` and `␣ ∈ Γ`, `␣ ∉ Σ`.
• δ : Q × Γ → Q × Γ × {L, R} — the transition function. Reading state `q` and tape symbol `a`, it outputs a new state, a symbol to write, and a head direction.
• q₀ ∈ Q — the start state.
• q_accept ∈ Q — the unique accept state.
• q_reject ∈ Q, with `q_reject ≠ q_accept` — the unique reject state.

`δ` need not be defined on every pair `(q, a)` — undefined transitions simply mean the machine halts (implicitly rejecting, or you can require totality by routing undefined cases explicitly to `q_reject`). Note that once the machine enters `q_accept` or `q_reject`, computation stops immediately: these are halting states, and `δ` is never consulted again.

Execution semantics

At every step the machine is fully described by a configuration: the current state, the entire tape contents, and the head position. Initially the tape holds the input string `w` starting at cell 1, with blanks everywhere else, the head is at cell 1, and the state is `q₀`. ``` PROCEDURE Run(M = (Q, Σ, Γ, δ, q0, q_accept, q_reject), w): tape ← array indexed by integers, all initialized to ␣ for i from 1 to length(w): tape[i] ← w[i] head ← 1 state ← q0 while True: symbol ← tape[head] if state == q_accept: return ACCEPT if state == q_reject: return REJECT if δ(state, symbol) is undefined: return REJECT # no legal move: implicit halt-and-reject (newState, writeSymbol, direction) ← δ(state, symbol) tape[head] ← writeSymbol state ← newState if direction == R: head ← head + 1 else: # direction == L head ← max(head - 1, 1) # cannot move left off the tape's start

# (some formulations instead treat this as a self-loop or error state;

# clamping at the left boundary is the standard convention)

# unreachable: loop only exits via ACCEPT/REJECT above

# if the machine never halts, this procedure never returns —

# that non-termination is the third possible outcome ``` Three, and only three, outcomes are possible for `M` run on `w`: it accepts (reaches `q_accept`), it rejects (reaches `q_reject`, or hits an undefined transition), or it loops forever. A language `L` is decided by `M` if `M` halts (accepts or rejects) on every input and accepts exactly the strings in `L`. A language is merely recognized (Turing-recognizable) if `M` accepts every string in `L` and does not accept any string outside `L`, but may loop forever on some non-members. This distinction — decide versus recognize — becomes central once you study configurations and computation histories in depth, and it underlies the undecidability of the Halting Problem.

A worked mini-machine

Consider deciding the language `L = {0ⁿ1ⁿ : n ≥ 0}` over `Σ = {0, 1}`. The classic strategy: repeatedly cross off the leftmost unmarked `0` and the leftmost unmarked `1`, alternating, until either both symbol types are exhausted together (accept) or a mismatch is found (reject). We use `Γ = {0, 1, x, ␣}` where `x` marks a crossed-off symbol. ``` States: q0 (find/mark a 0), q1 (scan right for matching 1), q2 (scan left back to start), q_accept, q_reject δ(q0, 0) = (q1, x, R) # mark leftmost unmarked 0, go find its 1 δ(q0, x) = (q0, x, R) # skip already-marked symbols δ(q0, 1) = (q_reject, 1, R) # a 1 appears before all 0s consumed -> mismatch δ(q0, ␣) = (q_accept, ␣, R) # nothing left unmarked -> all matched, accept δ(q1, 0) = (q1, 0, R) # skip remaining 0s δ(q1, x) = (q1, x, R) # skip marked symbols δ(q1, 1) = (q2, x, L) # found matching 1, mark it, turn around δ(q1, ␣) = (q_reject, ␣, R) # ran off the end with no matching 1 δ(q2, 0) = (q2, 0, L) # scan back left over 0s δ(q2, 1) = (q2, 1, L) # scan back left over 1s δ(q2, x) = (q2, x, L) # scan back left over marks δ(q2, ␣) = (q0, ␣, R) # hit left edge, restart the cycle ``` The invariant this machine maintains: after each full `q0 → q1 → q2` cycle, one more `0` and one more `1` have been marked `x`, and the unmarked region still looks like `0ⁱ1ⁱ` (or is exhausted). This is exactly the kind of loop invariant used to justify correctness for any Turing machine algorithm.

Time complexity. For a single-tape deterministic TM, the running time on an input of length `n` is defined as the number of steps (applications of `δ`) before the machine halts, maximized over all inputs of length `n` (worst case). There is no "average case" defined intrinsically by the model — complexity classes like `TIME(f(n))` are built directly on top of this step-count. The 0ⁿ1ⁿ example above uses `O(n)` full left-right sweeps, each sweep costing `O(n)` steps, giving `O(n²)` total steps — a single-tape TM cannot do better than quadratic for this language because each round trip is forced to re-scan the unmarked region; a multitape machine resolves this inefficiency, running the same task in `O(n)` steps, but note it accepts exactly the same language — the model changes speed, never what is decidable.

Space complexity. Space is measured as the number of distinct tape cells visited, again worst case over inputs of length `n`. Because the tape is unbounded, a TM can use more cells than its input length, unlike a finite automaton whose "memory" is fixed by its state count alone. This is precisely the extra power the tape provides.

Determinism and well-definedness. Because `δ : Q × Γ → Q × Γ × {L, R}` is a genuine function, the entire computation from a given input is uniquely determined: there is exactly one configuration sequence `C₀ ⊢ C₁ ⊢ C₂ ⊢ …` starting from the initial configuration `C₀`. This is the crux of why "the TM accepts `w`" is a meaningful yes/no/never-halts statement rather than an ambiguous one — contrast this with a nondeterministic model, where "accepts" means "some branch accepts."

Correctness argument (general pattern). To prove a TM decides a language `L`, you must show two things: 1. Every `w ∈ L` leads to `q_accept`. Typically shown via a loop invariant that holds after each pass through the main cycle, culminating in the halting condition that triggers the accept transition. 2. Every `w ∉ L` leads to `q_reject`. Shown by identifying every way the invariant can be violated (a mismatched symbol, running off the tape, wrong parity) and confirming each case is wired to `q_reject`. For the `0ⁿ1ⁿ` machine: the invariant "after `k` full cycles, exactly `k` `0`s and `k` `1`s are marked `x`, and the remaining unmarked prefix is `0^(n-k)1^(n-k)`" holds by construction of the `q0/q1/q2` cycle. When the invariant reaches `k = n`, `q0` reads `␣` and accepts. Any deviation — a stray `1` where a `0` is expected, or the tape ending mid-scan — is caught by the explicit reject transitions in `δ(q0, 1)` and `δ(q1, ␣)`. This case-exhaustive check is what makes the correctness proof airtight rather than merely plausible.

Honest tradeoffs. The Turing machine model says nothing about efficiency in practice — a real computer with random-access memory can be asymptotically faster for many tasks than a naive single-tape TM (e.g., array indexing is `O(1)` on real RAM but can cost `O(n)` head travel on a tape). This is why complexity theorists often use multitape TMs, or accept polynomial-time equivalence between models, as the working notion of "efficient," rather than insisting on literal single-tape step counts. The model's power is in universality and clean semantics, not raw speed.

Trace `M` (the `0ⁿ1ⁿ` decider above) on input `w = 0011`.

The invariant holds throughout: after cycle 1, one `0` and one `1` are marked (`n - k = 1` remaining unmarked pair); after cycle 2, both pairs are marked and the scan hits blank, confirming `n = 2` matched pairs — correctly accepting `0011 ∈ L`. Contrast with `w = 010` (not of the form `0ⁿ1ⁿ`): the very first `q1`-scan finds a `1` at position 2, marks it, reverses — but on the next `q0` pass, the machine reads the leftover `0` at position 3 sitting after a marked `1`, which under a careful implementation of `δ(q0, ·)` is detected as a leftover unmatched symbol of the wrong shape, or the scan structure otherwise reveals the mismatch, and the machine reaches `q_reject`. The essential point the trace demonstrates: determinism guarantees this exact sequence of configurations is the only possible run, so "does `M` accept `w`" is never ambiguous — it is simply a matter of executing the unique computation to its halting state.

The Turing machine is not directly implemented as physical hardware, but it is the yardstick against which every real computational system is measured. Compiler theory and programming-language semantics use TM-equivalence to justify that "Turing-complete" languages (Python, C, even certain configurations of spreadsheet formulas) can express any algorithm. Complexity theory — the entire landscape of P, NP, PSPACE, and the P vs NP question — is defined in terms of resources consumed by Turing machines (or their polynomially-equivalent variants). Cryptographic security proofs assume no polynomial-time TM can break a scheme, directly invoking this model. Compiler and interpreter designers, when reasoning about whether a language feature could cause infinite loops or undecidable type inference, are implicitly reasoning about Turing machines. Even practical questions like "can a static analysis tool prove this program terminates in all cases" trace back to the undecidability results Turing first established with this exact model.

Ask the tutor: How does a nondeterministic Turing machine's definition differ from the deterministic one, and why are they equally powerful despite that difference?