Configurations and Computation of Turing Machines

A configuration (also called an instantaneous description, ID) of a Turing machine is a complete snapshot of everything needed to resume computation: the state the machine is in, the entire contents of the tape, and where the head currently sits. Formally, if a machine has tape alphabet `Γ`, a configuration is written as a string ``` u q v ``` where `u ∈ Γ` is the tape contents to the left of the head, `q` is the current state, and `v ∈ Γ` is the tape contents from the head position onward (with trailing blanks conventionally omitted). The head is understood to be scanning the first symbol of `v`. This single-string encoding is deliberately chosen so that a configuration is itself just a string over `Γ ∪ Q`, which lets us later feed configurations into other Turing machines — a trick essential for constructing the Universal Turing Machine and for reductions. The start configuration on input `w` is `q₀ w`, meaning the machine begins in its start state `q₀` with the head on the leftmost symbol of the input and blanks filling the rest of the (conceptually infinite) tape. An accepting configuration is any configuration whose state is the accept state `q_accept`; a rejecting configuration is any configuration whose state is `q_reject`. Both are halting configurations: the transition function is never applied to them, so computation stops. Every other configuration is a non-halting configuration, and the transition function `δ` tells us exactly one thing to do next (for a deterministic machine) or a set of legal next moves (for a nondeterministic machine). The yields relation, written `C₁ ⊢ C₂`, holds when configuration `C₂` is produced from `C₁` by applying `δ` exactly once. Concretely, if `C₁ = u a q v` (head scanning symbol `a`, with `u` possibly empty) and `δ(q, a) = (q', b, D)`, then: ``` if D = R: C₂ = u b q' v (write b, move right, new state q') if D = L: C₂ = u' q' c v (write b, move left; u = u' c for some symbol c) ``` with the boundary case that moving left off the very start of the tape simply keeps the head at the leftmost cell (equivalently, some texts pad with a permanent left-end marker). The reflexive-transitive closure of `⊢`, written `⊢*`, relates a configuration to itself in zero steps and to any configuration reachable by a finite chain of single steps. A computation history of `M` on `w` is the (possibly infinite) sequence ``` C₀ ⊢ C₁ ⊢ C₂ ⊢ C₃ ⊢ ... ``` with `C₀ = q₀w`. Because a deterministic machine's `δ` is a (partial) function, this sequence, once `C₀` is fixed, is completely determined — there is exactly one computation history for `M` on `w`, and it either terminates in an accepting configuration, terminates in a rejecting configuration, or continues forever.

Building and tracing configurations is mechanical once you fix the encoding, but three design choices deserve explicit attention: how halting configurations are detected, how the tape grows, and how nondeterminism changes the picture (a single configuration can yield many successors, turning the computation history into a tree rather than a chain). The high-level procedure for simulating a TM and determining its verdict — accept, reject, or (if you bound the number of steps) "still running" — is: ``` function TRACE(M = (Q, Σ, Γ, δ, q0, q_accept, q_reject), w, maxSteps): C := configuration(left = "", state = q0, right = w) # C0 = q0 w step := 0 while step < maxSteps: if state(C) == q_accept: return ACCEPT, C, step if state(C) == q_reject: return REJECT, C, step (a, tail) := splitFirstSymbol(right(C)) # a = symbol under head if a is undefined: # right side exhausted a := BLANK tail := "" if δ(state(C), a) is undefined: return REJECT, C, step # implicit reject: no legal move (q', b, D) := δ(state(C), a) if D == RIGHT: newLeft := left(C) + b newRight := tail else: # D == LEFT if left(C) == "": newLeft := "" # head cannot move left of cell 0 newRight := b + tail else: (u', c) := splitLastSymbol(left(C)) newLeft := u' newRight := c + b + tail # note: c restored, b written before it C := configuration(left = newLeft, state = q', right = newRight) step := step + 1 return UNKNOWN, C, step # exceeded maxSteps: machine may be looping ``` A few points in this pseudocode are worth justifying line by line, because they are exactly where implementations go wrong: 1. Halting check comes first. Accept and reject states have no outgoing transitions, so we must test for them before consulting `δ`, otherwise we might try to look up a transition that does not exist. 2. Reading past the written tape yields a blank. The tape is conceptually infinite; only finitely many cells have ever been written. Treating an empty `right(C)` as scanning a blank symbol is what lets the machine "discover" the end of its input and write further right. 2. An undefined `δ(q,a)` is an implicit reject. Many presentations require `δ` to be total on non-halting states for a well-formed machine, but robust simulators treat missing transitions as immediate rejection rather than crashing — this matches the standard convention that computation halts and rejects if no move applies. 3. Left moves at the tape's start cell are idempotent. There is no cell to the left of cell 0, so the standard convention is that the head simply stays put (some formalizations instead forbid this transition in `δ`, or use a fixed left-end marker `⊢` that the machine may never move past). 4. `maxSteps` is a simulation artifact, not part of the model. Real Turing machines have no step bound; the parameter exists only so this pseudocode terminates, letting us distinguish "accepted/rejected within the bound" from "we don't yet know" — we can never soundly conclude "loops forever" from a bounded trace, which is precisely the content of the undecidability of the Halting Problem. The picture below shows one configuration, the yields step applied to it, and the resulting configuration, laid out as an explicit tape-and-head diagram so the string encoding `u q v` and the "physical" tape picture match up.

Nondeterministic Turing machines generalize `δ` to return a set of legal `(q', b, D)` triples. A single configuration can then yield several distinct successor configurations, so the computation "history" becomes a computation tree: the root is `C₀ = q₀w`, and each node's children are its `⊢`-successors. The convention that defines acceptance for nondeterministic machines is existential: `M` accepts `w` if some branch of this tree reaches an accepting configuration, regardless of what other branches do (even if some loop forever). This is what makes nondeterministic machines equivalent in power, but not obviously equivalent in efficiency, to deterministic ones — the subject taken up when comparing Multitape Turing Machines and other TM variants. With configurations, yields, and computation histories in hand, we can finally state the definition that the rest of computability theory is built on. Machine `M` accepts string `w` if there exists a finite computation history `q₀w ⊢ C` where `C` is an accepting configuration. `M` <strong>rejects</strong> `w` if there is a finite computation history `q₀w ⊢ C` where `C` is a rejecting configuration. Otherwise — if every computation history from `q₀w` is infinite — `M` loops on `w` (this is often called "looping forever" or "diverging," and is not an error state; it is a legitimate, if unproductive, behavior of the machine). The language recognized by `M` is ``` L(M) = { w ∈ Σ* : M accepts w } ``` Note carefully: `L(M)` says nothing about strings on which `M` loops. A string not in `L(M)` might be rejected, or the machine might simply never finish deciding. This asymmetry — accept is a positive, observable event; non-acceptance is not — is precisely why Turing-recognizable languages and decidable languages are different classes, a distinction developed fully in Decidable and Turing-Recognizable Languages.

Well-definedness (determinism). For a deterministic Turing machine, `δ : Q × Γ → Q × Γ × {L, R}` is a partial function, so at any non-halting configuration `C`, there is at most one triple `(q', b, D)` available, hence at most one configuration `C'` with `C ⊢ C'`. By induction on the length of the computation history, the entire sequence `C₀, C₁, C₂, ...` is uniquely determined by `C₀` (equivalently, by `M` and `w`). This is the formal reason we may speak of "the computation of `M` on `w`" rather than "a possible computation" — a phrase that is only meaningful, without qualification, for deterministic machines.

Trichotomy is exhaustive and mutually exclusive. Accepting and rejecting configurations are disjoint by definition (`q_accept ≠ q_reject`), and both are terminal (no transition is defined out of them), so a computation history cannot both accept and reject, nor can it accept/reject and also continue forever — once a halting configuration appears, the sequence stops there. If no halting configuration ever appears, the sequence is infinite, i.e. the machine loops. These three cases are exhaustive because the sequence `C₀, C₁, C₂, ...` is either finite (ending in a halting configuration, since only halting configurations lack a successor) or infinite. This is not an extra assumption; it follows purely from the definition of `⊢` and the fact that `q_accept, q_reject` are the only states without transitions.

`L(M)` is well-defined as a set. Membership `w ∈ L(M)` depends only on the (unique, for deterministic `M`) computation history starting at `q₀w`, so it is a genuine yes/no fact about `w`, not something that depends on how we simulate `M`. Different simulators, different encodings of configurations, different tie-breaking — none of it changes whether an accepting configuration is eventually reached, because that reachability is determined purely by `δ` and `w`.

Time and space cost of simulating one yields-step. Representing a configuration as an explicit string of length `n` (tape contents) plus a state marker, a single application of `⊢` (as coded in `TRACE` above) costs: ``` O(n) time — splitting/rebuilding the left or right tape strings O(1) extra space beyond the configuration itself (ignoring string-copy overhead) ``` if configurations are stored as plain strings copied on every step. This can be improved to amortized `O(1)` time per step with a doubly-linked-list or two-stack tape representation (`left` as a stack, `right` as a stack, popping/pushing on head moves), since only the cells adjacent to the head are touched. Either way, a full trace of `t` steps costs `O(t)` time with the efficient representation, or `O(t · n_max)` with naive string rebuilding, where `n_max` is the longest tape length reached. Space used by the trace itself is bounded by the length of the longest configuration reached, which is at most `O(t)` since each step writes at most one new symbol.

Honesty about the fundamental limit. No algorithm can decide, in general, whether the third outcome (looping) will occur — this is exactly the undecidability of the Halting Problem. The `maxSteps` bound in `TRACE` is therefore not a limitation of our pseudocode specifically; it reflects a hard mathematical boundary. Any simulator that always terminates with a definitive "accept / reject / loops forever" verdict for every machine and input would itself decide the halting problem, which is impossible. This is why `TRACE` returns `UNKNOWN` rather than ever asserting "loops forever."

Consider a tiny deterministic Turing machine `M` over `Σ = {0, 1}`, `Γ = {0, 1, ␣}`, deciding the language of strings with an even number of 1s. States: `q0` (start, "seen even 1s so far"), `q1` ("seen odd 1s so far"), `q_accept`, `q_reject`. Transition table:

We trace `M` on input `w = 101`. Configurations are written `u [q] v` with the bracket marking the head's scanned symbol (the first symbol of `v`).

The computation history is `q0 101 ⊢ 1q101 ⊢ 10q11 ⊢ 101q0␣ ⊢ 101␣q_accept`, a finite chain of length 4 ending in an accepting configuration, so `M` accepts `101` and `101 ∈ L(M)` — correctly, since `101` contains exactly two `1`s (even). Now trace `w = 110` to see a rejecting path:

`110` has two `1`s (even), so acceptance is again correct — a useful reminder that "accept" traces don't need to look identical to be right; what matters is that the parity bookkeeping in the state matches the actual count. Finally, `w = 1` (one `1`, odd) drives the machine to `q1` and then to `q_reject` on the blank, correctly rejecting. In every case the machine halts in at most `|w| + 1` steps — there is no danger of looping here because every state has a defined transition on every symbol in `Γ`, so this particular `M` always halts, making it not just Turing-recognize but decide its language, foreshadowing the decidable/recognizable distinction.

The concept of a configuration formalizes, in modern notation, the "complete configuration" that Alan Turing described narratively in his 1936 paper as the state, the tape's symbols, and the scanned square — the very same idea later sharpened into the string-based instantaneous description used in every modern treatment, including the standard undergraduate formulation by Michael Sipser.

The configuration/yields formalism is not merely a proof-theoretic nicety; it is the template every real model-checking and interpreter-correctness argument follows. Operating-system schedulers reason about "process states" the same way — a full snapshot of registers, memory, and program counter, with a step relation between snapshots, exactly mirroring `u q v` and `⊢`. Formal verification tools (model checkers like SPIN or TLA+) represent a system's entire state as one object and explore the reachable-state graph, precisely generalizing the computation tree of a nondeterministic Turing machine. Compiler and virtual-machine correctness proofs (e.g., proving a bytecode interpreter faithfully executes source semantics) are typically stated as: "the configuration sequence of the compiled program simulates the configuration sequence of the source program," a direct descendant of the yields relation defined here. And the accept/reject/loop trichotomy is the seed of practical static-analysis tool design: type checkers and linters are engineered to always halt (deciders), deliberately sacrificing completeness to avoid the looping branch that a general Turing-machine simulator cannot rule out — a design tension traceable straight back to the Halting Problem.

Ask the tutor: How does the definition of the yields relation change when a Turing machine has multiple tapes, and why does that variant still recognize exactly the same languages?