Turing Machines, Universality & Decidability

Calling a language “Turing-complete” is not praise, a speed claim, or a promise that it can solve every problem. It is a precise claim about which partial functions an idealized computational system can realize, once programs, inputs, outputs, termination, divergence, and available storage have all been fixed. The label is useful only after those hidden choices are made explicit.

Sellin's explainer surfaces many of the right engineering questions: how a machine description becomes data, why physical memory bounds matter, and what undecidability means for compilers. This chapter rebuilds the answer from primary sources and corrects three common conflations:

1. a formal model is not one physical device;
2. equivalence between formal models is not the Church-Turing thesis;
3. universality is not efficiency or decidability.

First fix the object receiving the label #

The word “system” can hide several different objects.

A language specification may describe arbitrarily large finite values even though every implementation eventually runs out of memory. Conversely, a program may call an external oracle-like service whose behavior is not part of the language's effective core. “The language is Turing-complete” therefore needs a semantic model, not a screenshot of one successful program.

The Turing-machine mechanism #

A standard deterministic single-tape Turing machine is a tuple

$$M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\mathrm{acc}},q_{\mathrm{rej}}),$$

where:

• $Q$ is a finite set of control states;
• $\Sigma$ is the input alphabet;
• $\Gamma\supseteq\Sigma$ is a finite tape alphabet containing a blank symbol $\square$;
• $q_0$ is the start state and $q_{\mathrm{acc}},q_{\mathrm{rej}}$ are halting states;
• the transition function is

$$\delta:(Q\setminus\{q_{\mathrm{acc}},q_{\mathrm{rej}}\})\times\Gamma \longrightarrow Q\times\Gamma\times\{L,R,S\}.$$

If $\delta(q,a)=(q',b,R)$, one step replaces the scanned $a$ with $b$, changes the finite control to $q'$, and moves the head one cell right. The optional stay-put move $S$ is a convenience; models without it simulate it with a short left-right detour. One-way tapes, two-way tapes, multiple tapes, and several other conventional variations differ in convenience and cost, not in computability.

flowchart TB
    Q["Finite control in state q"] --> D["Transition rule δ(q,a) = (q',b,R)"]
    D --> W["Write b in the scanned cell"]
    W --> M["Move the head one cell right"]
    M --> N["Continue in state q'"]
    T0["... tape cell ..."] --- T1["left symbol"] --- T2["a — scanned"] --- T3["right symbol"] --- T4["... tape cell ..."]
    D -. reads .-> T2

A complete configuration contains everything needed to determine the future: current state, head position, and tape contents. Although the tape has unbounded potential extent, every configuration reached after finitely many steps has touched only finitely many cells. “Unbounded” means that no single fixed ceiling is imposed on all inputs and runs; it does not mean that one computation occupies an actually completed infinity of memory.

A trace is not a universality proof #

Consider a unary successor machine with two rules:

$$\begin{aligned} \delta(q_{\mathrm{scan}},1)&=(q_{\mathrm{scan}},1,R),\\ \delta(q_{\mathrm{scan}},\square)&=(q_{\mathrm{acc}},1,S). \end{aligned}$$

On input 111, its configurations progress schematically as

$$(q_{\mathrm{scan}},[1]11) \vdash(q_{\mathrm{scan}},1[1]1) \vdash(q_{\mathrm{scan}},11[1]) \vdash(q_{\mathrm{scan}},111[\square]) \vdash(q_{\mathrm{acc}},111[1]).$$

This explains state, tape, head, and one-step semantics. It proves only that this particular machine computes unary successor. Universality requires a construction that works for every encoded machine, not an impressive trace or a long-running loop.

Recognition, decision, and partial functions #

The same transition mechanism supports several observational conventions.

• A recognizer accepts strings in a language; on nonmembers it may reject or diverge.
• A decider halts on every input and answers yes or no.
• A transducer halts with an encoded output, thereby computing a partial function.

The explicit accept/reject states in the tuple above are a modern language-recognition convention, not a compulsory feature of every Turing-machine definition. Turing's original machines produced sequences and distinguished circular from circle-free behavior. Halting, accepting, rejecting, printing infinitely many designated figures, and computing a partial function are different observation rules that must not be exchanged without a reduction.

For a program $p$, write

$$\llbracket p\rrbracket:\mathbb N^k\rightharpoonup\mathbb N.$$

$\llbracket p\rrbracket(\vec x)\downarrow=y$ means that the computation halts with output $y$; $\llbracket p\rrbracket(\vec x)\uparrow$ means that it produces no natural-number output. Pure partial-function semantics collapses all such undefined cases, so an unobserved stuck state and divergence may be extensionally identical. A stronger operational simulation normally preserves stepwise progress and divergence. If timeout, exception, rejection, or resource exhaustion is observable, that outcome must be included in the semantics and cannot silently replace an infinite run.

The chapter on recursive functions and computable enumerability develops this partial-function view, decidable versus c.e. sets, dovetailing, and the full diagonal proof for the halting set. Here the focus is the machine and simulation boundary.

Why the tape changes the power boundary #

A finite automaton has finitely many states and no separately growing work store. After reading an input prefix, all remembered information must be compressed into one of those states. That is why it recognizes exactly the regular languages.

A Turing machine still has finite control, but it may externalize an arbitrarily large finite amount of intermediate information onto the tape. It can revisit, update, copy, and compare that information. The decisive change is not “its control graph has a cycle”—a DFA can have cyclic transitions, and a finite-state machine with internal steps can loop—but that the family of possible Turing configurations is not capped in advance across all inputs and runs.

Programs become data #

Turing's 1936 construction first normalizes every finite machine table into a standard description, then encodes that description as a number. The exact alphabet and numeral convention are incidental. The load-bearing facts are:

1. every program has a finite code $\langle M\rangle$;
2. encoding and decoding are mechanical;
3. a simulator can recover the next transition from the code;
4. codes can be inputs to other programs.

The code identifies a finite description, not a computed function canonically. Renaming states, inserting unreachable transitions, or choosing another algorithm yields different codes with the same extensional behavior. Some natural numbers may also fail to decode as valid descriptions under a chosen syntax. Universality needs an effective numbering, not a unique behavioral fingerprint.

Turing then constructs a single universal machine $U$ such that, schematically,

$$U(\langle M\rangle,x)\simeq M(x),$$

where $\simeq$ denotes a deliberately strong operational relation: the two sides have the same result when they halt and either both diverge or both continue producing the same infinite sequence under the chosen convention. Equality as partial functions is weaker—it requires the same natural-number result, or no such result on both sides, without necessarily distinguishing divergence from an unobserved exceptional stop.

In programming-language notation, a universal interpreter $u$ satisfies

$$\llbracket u\rrbracket(\langle p,x\rangle)\simeq\llbracket p\rrbracket(x).$$

This is the conceptual ancestor of stored programs: instructions and ordinary data share an effective representation. It is also what makes self-application and diagonal arguments possible.

The exact completeness claim #

Let $S$ be a system with a countable set of finite programs and computable encodings of finite inputs and outputs.

Lower bound: every Turing computation can be expressed #

$S$ is at least Turing-powerful if, for every Turing machine $M$, an effective compiler produces a program $C(M)$ such that

$$\llbracket C(M)\rrbracket_S(\mathop{\mathrm{enc}}(x)) \simeq \mathop{\mathrm{enc}}(\llbracket M\rrbracket(x)).$$

The compiler itself must be an algorithm. Otherwise a noncomputable choice of target program could hide the very power being claimed.

Upper bound: the target has no stronger primitive #

To conclude equality, the operational semantics of $S$ must also be effectively simulable by a Turing machine. A finite syntax with computable step rules normally makes this routine. It is not routine if the language includes exact equality on arbitrary real numbers, a halting oracle, an infinite advice table, or an external service whose behavior has not been modeled.

flowchart TB
    TM["Turing machine M and input x"] --> C["Effective compiler"]
    C --> SP["Target program C(M) with enc(x)"]
    SP --> O["Same output y or same divergence"]
    SS["Effectively specified target semantics"] --> I["Turing-machine interpreter"]
    I --> TR["Matching target execution"]

The left path proves a lower bound: the target can express every Turing computation. The right path supplies the upper bound. Together they establish the same class of partial functions.

Equivalent formulations #

With ordinary effective encodings, the following formulations align:

• simulate every Turing machine;
• compute every partial recursive function;
• recognize every computably enumerable language;
• implement a universal evaluator for a known Turing-complete source model.

The equivalence is a theorem between formal models. Turing's 1937 paper proves the equality of Turing-computable, lambda-definable, and general-recursive functions. It is not merely a family resemblance.

How to prove a system Turing-complete #

Three proof patterns recur.

1. Simulate a Turing machine directly #

Encode the transition table, state, tape, and head. Prove by induction that after $k$ source steps, the target representation denotes the same configuration. Then show that halting states, output extraction, and infinite runs correspond.

2. Compile a known universal core #

Implement every primitive instruction of an already universal machine model, such as a register machine with suitably unbounded counters. Give a total effective compiler and an invariant relating source registers and control locations to target values and program points.

3. Build a universal interpreter #

Accept an effective code for arbitrary programs in a known universal model. Decode one source instruction at a time and preserve the simulated state. A hand-written interpreter is evidence only after its source model, input encoding, resource assumptions, and divergence behavior are all specified.

A direct operational simulation proof normally discharges these obligations. For a claim only about extensional partial functions, the divergence row weakens to preservation of defined versus undefined output under the declared observation rule.

Worked universality construction: represent the tape by two stacks #

Suppose a target language has finite control, finite maps, loops, and two stacks that may grow without a fixed semantic bound. Represent a Turing configuration by:

• state: the current machine state;
• left: symbols strictly left of the head, nearest symbol on top;
• current: the scanned symbol;
• right: symbols strictly right of the head, nearest symbol on top;
• delta: the finite encoded transition table.

One interpreter iteration is:

(next_state, written, direction) = delta[(state, current)]

if direction == R:
    left.push(written)
    current = right.pop_or(blank)
else if direction == L:
    right.push(written)
    current = left.pop_or(blank)
else:
    current = written

state = next_state

The invariant is exact: before each iteration, reversing left, then appending current, then right, reconstructs the simulated tape around the head; state is the simulated control state. Each branch implements precisely one Turing transition in finitely many target operations. Induction on the number of iterations gives configuration correspondence for every finite prefix of the run.

If the simulated machine halts, the interpreter reaches the same halting state and its stacks encode the same tape output. If the machine takes another step forever, the interpreter continues taking iterations forever. Because the transition table is finite but the stacks may grow as required, the construction handles every finite Turing-machine description and every finite input.

This establishes the lower bound for any language that can realize the interpreter faithfully. To establish equality, show that the target's own stack, map, control, and arithmetic operations are effective and can be simulated by a Turing machine.

The physical and semantic resource boundary #

flowchart TB
    F["Fixed device<br/>Finite global configuration set<br/>Not Turing-universal"]
    L["Linear-bounded automaton<br/>At most c·n cells for input length n<br/>Universal only within a restricted class"]
    T["Turing model<br/>No fixed or input-derived work-tape ceiling<br/>Can support a universal simulation"]
    F --> L --> T

A fixed physical computer is finite-state #

Close the system boundary around a device with $B$ mutable bits, finitely many control states, and finite peripheral state. It has only finitely many global configurations—at most a fixed product containing $2^B$. A deterministic run that has not halted before repeating a configuration will repeat the same future forever. In principle, termination on that fixed device is decidable by exploring this finite graph, even though the graph is astronomically too large for practical use.

That device is therefore not literally Turing-complete. Engineering usage idealizes away the ceiling: for every finite computation needing more memory, imagine a larger conforming implementation. This is a statement about a family or semantics, not one box on a desk.

A linear-bounded automaton is a different boundary #

A linear-bounded automaton (LBA) may use at most $c\lvert x\rvert$ tape cells for an input $x$, for some machine-dependent constant $c$. Its available memory grows across the input family but is finite for each fixed input. That is not the same as a globally fixed tape, and it is not the same as a Turing tape with no input-derived ceiling.

For a fixed LBA and input, the configuration graph is finite, so acceptance can be determined by reachability. LBAs characterize a restricted language family associated with context-sensitive grammars; they are not Turing-complete. Saying that a finite-tape machine “is an LBA” without specifying how the bound scales with input length conflates three different models.

Language specifications and implementations #

A language-level universality claim normally assumes:

• arbitrarily large but finite inputs;
• integers, strings, lists, heaps, or stacks that can grow as needed;
• no fixed recursion-depth or allocation ceiling in the abstract semantics;
• exact behavior for the operations used by the simulation.

An actual runtime adds word overflow, maximum object sizes, address-space limits, stack caps, allocation failure, timeouts, undefined behavior, and operating-system termination. Those implementation outcomes may prevent a particular run from matching the ideal semantics. They do not retroactively change the formal expressiveness theorem; they change which theorem applies to the concrete implementation.

Countability already forces an incomputable outside #

The prerequisite chapter on countability supplies the diagonal argument used here.

Every finite program is a finite string over a finite or countable alphabet, so the set of programs is countable. Each deterministic program denotes at most one partial function under fixed semantics. But the set of total functions

$$f:\mathbb N\to\{0,1\}$$

is uncountable: each such function is the characteristic function of a subset of $\mathbb N$, and Cantor's diagonal argument shows that the power set of $\mathbb N$ is uncountable. Therefore no programming system with finite descriptions can denote every mathematical function of that type.

This proves that uncomputable functions exist without identifying a useful example. The halting construction goes further: it defines a concrete behavior question and proves that no program decides it. Calling “almost all functions” uncomputable is safe only in this cardinal sense unless a probability measure has also been specified.

Universality brings undecidability #

Let

$$\mathrm{HALT}_{TM}=\{\langle M,x\rangle:M\text{ eventually halts on }x\}.$$

No Turing machine decides this set for all pairs. The familiar diagonal proof assumes a total decider, constructs a program that does the opposite when applied to its own code, and obtains a contradiction. The full modern proof lives in recursive functions and enumerability.

Historical wording matters. Turing's 1936 paper did not state the modern predicate in exactly this notation. It first proved that no machine decides whether an arbitrary description is circle-free, meaning that it prints infinitely many designated figures. This infinitary liveness property is distinct from ordinary halting. Turing then proved that no machine decides whether an arbitrary machine ever prints a specified symbol. That reachability problem is directly interreducible with modern halting by routine effective constructions. “Turing proved the halting problem undecidable” is therefore accurate modern shorthand only when this historical distinction is kept in view.

A Turing-complete target inherits this limit. If target programs had a total halting decider, compile $M$ and $x$ into the target, ask the target decider, and thereby decide $\mathrm{HALT}_{TM}$. The same simulation that establishes expressive power transports the impossibility result.

Rice's theorem: the general semantic boundary #

Fix an acceptable enumeration $\varphi_0,\varphi_1,\ldots$ of partial computable functions. Let $\mathcal C$ be an extensional property: membership depends only on the partial function computed, not on spelling, instruction count, comments, or compilation history. If $\mathcal C$ is nontrivial—some partial computable function has it and another does not—then the index set

$$I_{\mathcal C}=\{e:\varphi_e\in\mathcal C\}$$

is undecidable.

The reduction exposes every hypothesis. Let $\bot$ be the nowhere-defined function and, without loss of generality, suppose $\bot\notin\mathcal C$; otherwise use the complement property. Choose a computable $g\in\mathcal C$. Given an alleged halting instance $(e,x)$, effectively construct a program $P_{e,x}$ that on input $y$:

1. simulates $\varphi_e(x)$;
2. if that simulation halts, computes $g(y)$;
3. otherwise continues waiting forever.

Then

$$\varphi_{P_{e,x}}= \begin{cases} g,&\varphi_e(x)\downarrow,\\ \bot,&\varphi_e(x)\uparrow. \end{cases}$$

A decider for $I_{\mathcal C}$ would therefore decide halting. This contradiction proves the theorem.

Examples of nontrivial extensional questions covered by Rice's theorem include:

• “Does this program compute the constant-zero partial function?”
• “Is its computed partial function total?”
• “Does it accept any input?”

Equality of the partial functions computed by two arbitrary programs is also undecidable. This is an immediate corollary: if arbitrary pairs could be compared, one side could be fixed to a program for the constant-zero function, deciding one of the Rice properties above.

Questions not covered merely by invoking Rice include:

• “Does the source contain a multiplication opcode?”—syntactic;
• “Does it halt within 10,000 steps on this input?”—bounded simulation decides it;
• “Is the control-flow graph acyclic?”—a finite graph property;
• “Does this restricted non-universal language terminate?”—the language may enforce a decidable fragment.

Rice's theorem does not say static analysis is futile. It says no terminating analyzer can be both sound and complete for every nontrivial extensional property of arbitrary programs in a universal model. Practical analyzers restrict the language, restrict the property, accept false positives or negatives, require annotations/proofs, or decide bounded cases.

What Turing completeness does not imply #

Hartmanis and Stearns made the resource distinction explicit: computability asks whether a result is obtainable at all; complexity asks how time and storage grow. A slow universal interpreter and an optimized compiler may compute the same partial functions while differing radically in practical cost.

Formal equivalence versus the Church-Turing thesis #

Three statements are often collapsed:

1. Formal theorem: Turing machines, lambda calculus, and general recursive functions compute the same partial functions under effective encodings.
2. Church-Turing thesis: every informally effective calculation is captured by that formal class.
3. Physical or cognitive claim: every process in nature, or every act of human reasoning, is simulable by a Turing machine.

Only the first is an ordinary theorem between defined mathematical systems. The second relates a formal definition to the preformal notion of effective calculability. Turing's own section on the “extent” of computable numbers explicitly describes the supporting arguments as appeals to intuition, equivalence with other analyses, and broad examples. The third is stronger still and needs independent empirical and philosophical premises.

The convergence of independently motivated models is powerful evidence for the thesis. It is not a proof obtained merely by listing equivalent formalisms. The recursive-functions chapter owns the fuller account of that convergence.

Oracles are relative computation, not a higher completeness grade #

An oracle Turing machine may ask membership questions about a fixed set $A$ in one idealized step. It computes functions relative to $A$. If $A$ is the ordinary halting set, that oracle answers questions no ordinary Turing machine can decide—but a new diagonal construction produces a halting problem relative to $A$ that this oracle still cannot decide.

Calling such a system “super-Turing-complete” obscures the structure. The standard language is oracle computation, Turing reducibility, and Turing degrees. Writing an oracle primitive into a language specification does not implement it physically or make the rules effective; it changes the mathematical model by assumption.

Why deliberately incomplete languages matter #

Universality is often unnecessary or actively undesirable.

• Regular expressions in the formal-language sense describe regular languages and have decidable equivalence and inclusion procedures.
• Query and policy languages may restrict recursion to make termination or planning decidable.
• Total functional languages accept only definitions with a termination argument.
• Hardware-description, build, configuration, and authorization DSLs often benefit from predictable resource use more than unrestricted expressiveness.

Removing general recursion or unbounded mutation does not automatically make every interesting property decidable, but a carefully designed restriction can make particular analyses complete. Expressiveness and analyzability are a trade, not a maturity ladder.

Audit a Turing-completeness claim #

Before accepting the label, answer all of these:

1. What is the object? A formal model, language semantics, one interpreter, one runtime, or one physical device?
2. What are inputs and outputs? Are their encodings finite, injective where needed, and computable in both directions?
3. Where is unbounded-on-demand storage? A stack, tape, heap, counter, or growing term must lack a fixed semantic cap.
4. What known universal model is simulated? Name it and give an effective translation.
5. What is the invariant? Explain how target states represent source configurations after each step.
6. What equivalence is claimed? At minimum preserve defined versus undefined output; for operational simulation, preserve halting, output, and divergence separately. Successful examples alone are insufficient.
7. Is there an upper bound? Can a Turing machine effectively simulate every target primitive?
8. Is an oracle hidden? Exact real arithmetic, infinite tables, and external services require separate modeling.
9. Is universality only relative to a restricted class? A universal regex interpreter is not a universal Turing machine.
10. Is the claim actually about efficiency or safety? If so, Turing completeness is the wrong theorem.

The durable mental model is compact: finite programs plus effective encodings make programs data; an unbounded-on-demand work store can support a proved universal simulation; and once a system can express every computable behavior, no algorithm can decide every nontrivial extensional semantic property of its programs.