Turing Completeness

## What the term actually claims A model of computation is **Turing complete** when it can simulate an arbitrary Turing machine: for every machine and every input there is something you can mechanically construct in the model whose evaluation reproduces that run — the same result when the machine halts, and no result when it does not. The claim is about **which functions** the model can compute. It says nothing about speed, memory use, or whether the model is pleasant to write in. Most models anyone asks about are also **Turing equivalent**: complete, and simulable *by* a Turing machine, so the two compute exactly the same class of functions. The direction is the easiest thing here to get backwards: - Simulating a Turing machine **inside** your model proves your model is **at least as powerful**. - Simulating your model **on** a Turing machine proves it is **no more powerful**. - Only both together give equality. The phrase *Turing complete* names the first direction alone. ## Why simulation is the only usable test You cannot establish completeness by listing the functions a model computes and ticking them off — the set is infinite and has no finite checklist. So every completeness argument is a **reduction**: take a model already known to be complete, and build an interpreter for it inside the candidate. If the candidate can run that interpreter, it can run anything that model can run, and completeness transfers to the candidate. That is why the same handful of small witnesses keeps appearing in these arguments. | Model | What holds the state | What one step does | |---|---|---| | Turing machine | a tape, a head position, a control state | rewrite the current cell, move the head, change state | | Lambda calculus | a single term | reduce one redex by substituting an argument into a body | | Register machine | finitely many unbounded counters | increment, or decrement-and-branch-if-zero | | Tag system | a queue of symbols | delete a fixed-length prefix, append a word chosen by the first symbol | | Cellular automaton | a line of cells with a fixed neighbourhood rule | update every cell simultaneously from its neighbours | A register machine with two unbounded counters and those two instructions is already complete, given a suitable encoding of the input. That is why it is usually the cheapest target: you only have to show the candidate can hold an unbounded number, test it against zero, and jump on the result. ## What a completeness argument looks like in practice 1. **Pick the target.** A counter machine or a bare applicative core, because each has a tiny instruction set and correspondingly little to encode. 2. **Find the three ingredients** in the candidate: unbounded storage, a conditional, and repetition whose number of iterations is not fixed in advance — general recursion, or a loop whose continuation depends on a computed value. 3. **Exhibit the encoding.** Say how a target state is represented in the candidate, and how one target step becomes one or more candidate steps. 4. **Check that nothing caps the run.** A fixed recursion depth, a fixed iteration count, or a ceiling on value size that no input can raise defeats the simulation. Such a system is *not* complete; it is a bounded approximation of a complete one, and every one of its evaluations terminates by construction. Step 4 is where real systems land. Take away the unbounded storage and you fall back to something a finite-state recogniser could do; take away unbounded repetition and evaluation always terminates, which is usually the property a format's designers wanted in the first place. ## The finiteness objection Every physical implementation has finite memory, so strictly speaking it is an enormous finite-state machine and not a Turing machine at all. That is true and mostly unhelpful. The label is applied to the **model** — the language as specified, with no bound written into it — and the point of the label is precisely that *the specification imposes no bound*, so no inspection of a program text tells you how long an arbitrary input will take. A candidate who answers "but real machines are finite" and stops has dodged the question rather than answered it. ## What completeness does not buy you - **Not speed.** Two complete models can differ by any amount of work on the same problem; the equivalence constrains the computable set, not the cost. - **Not engineering expressiveness.** A complete model may make ordinary tasks miserable. *Complete* and *convenient* are unrelated properties. - **Not capability.** Reading a file, opening a socket or reading a clock are not computation; a complete model has none of them unless something outside the model supplies them. - **Not analysability.** Crossing into completeness is exactly where an evaluator loses the ability to bound its own work by looking at its input — which is why formats that carry untrusted content treat the crossing as a decision, not a feature.