Symptom

Somebody says “CSS is Turing-complete” and the room splits. Half the people treat it as a joke about a styling language, the other half as a serious claim with consequences. Both reactions are common and only one is right.

The same phrase turns up in places that matter. Your YAML configuration language grew conditionals and templating, and now someone claims it is Turing-complete and therefore you can no longer statically check deployment configs. Your database migration DSL acquired loops. A security researcher demonstrates computation inside x86’s MMU fault handler, or inside printf format strings, or in Magic: The Gathering. Every one of these is presented as though it establishes something.

The trouble is that “Turing-complete” sounds like a statement about speed, or expressiveness, or practicality, and it is none of those. It is a statement about a boundary, and understanding why the boundary exists at all — why there is a single line rather than a spectrum of computational power — requires the one entry in this series that is not a theorem.

Statement

Every function that is effectively calculable — computable by any mechanical procedure a human or machine could carry out with unlimited time and paper — is computable by a Turing machine.

That is the thesis. Note carefully what it is not: it is not a theorem, and cannot be, because “effectively calculable” is an informal notion. The thesis identifies an intuitive concept with a formal one, and that identification is not the kind of thing a proof can establish. It is an empirical and conceptual claim, and after ninety years it is as well-supported as anything in science.

The formal half of the story is a theorem, and a striking one: all of the proposed formalizations of computation are equivalent. Turing machines, Church’s $\lambda$-calculus, Gödel and Herbrand’s general recursive functions, Post’s canonical systems, register machines, cellular automata, tag systems, and every real programming language compute exactly the same set of functions. Not similar sets. The same set.

This gives the practical corollary that people mean when they use the phrase: a system is Turing-complete if it can simulate a Turing machine, and any two Turing-complete systems can simulate each other. Turing-completeness is not a degree. You have it or you do not, and if you have it you have all of it.

Argument

The thesis rests on three legs, and they are worth separating because people usually only know the first.

Confluence. In 1936, three people independently formalized computation from completely different starting points. Church built the $\lambda$-calculus from function abstraction and application. Gödel and Herbrand defined general recursive functions from equations over the naturals. Turing built an idealized clerk with a tape. These have no surface resemblance whatsoever — one is symbolic rewriting, one is number theory, one is a machine — and they were proved equivalent almost immediately. Since then, every new model has landed in the same place: quantum computers change the efficiency landscape and compute exactly the same functions; DNA computing, membrane computing, and the various unconventional models all fall in. Ninety years of people trying to escape, nobody escaping.

Turing’s own argument, which is the actually convincing one. Turing did not argue from examples. In section 9 of his 1936 paper he analyzes what a human computer — the job title, a person doing calculation with pencil and paper — physically can do. The observations: a person can only distinguish finitely many symbols, because arbitrarily similar symbols become indistinguishable; can only be in finitely many states of mind, for the same reason; can only attend to a bounded portion of the workspace at once; and can only move attention a bounded distance in one step. Every one of those is a claim about finite physical beings, not about mathematics. Given all four, the behaviour is exactly a Turing machine. This is a derivation from physical constraints, which is why the thesis feels like more than a coincidence.

Robustness under modification. Adding power to the Turing machine does not add power. Multiple tapes, two dimensions, nondeterminism, randomness, unbounded parallelism: each is simulable, usually with polynomial overhead (nondeterminism costs exponential time but not computability). Models designed to be tiny are equally powerful — Rule 110, the two-counter Minsky machine, the SKI combinators, Conway’s Game of Life. The class is stable in both directions, which is what you expect of something natural rather than arbitrary.

Why the line is sharp. The reason Turing-completeness is binary is that once a system can do a small handful of things — store unbounded state, branch on it, and loop — it can interpret a universal machine (T013), and thereby simulate any computation at all. There is no way to have half of that. The accidental Turing-completeness of printf and the x86 MMU is a consequence: the threshold is so low that stumbling over it is easy.

Forbids

No physical device computes more than a Turing machine. This is the thesis’s real content. Every impossibility result that follows in Part II — the halting problem, Rice’s theorem, undecidability of first-order validity — inherits its scope from here. Without the thesis, “no Turing machine can decide halting” is a narrow statement about one formalism; with it, it is a statement about everything you could ever build.

No programming language is more expressive than another, in the sense of which functions it can compute. Assembly and Haskell compute the same set. Arguments about language power are arguments about ergonomics, safety, and concision — real things, but not this.

No amount of DSL restraint helps once you cross the line. If your config language is Turing-complete, then “does this config terminate?” and “does it ever access this resource?” are undecidable (T011). You do not get to be slightly Turing-complete and keep your static analysis.

Does not forbid

It does not say all models are equally efficient, and this is the most consequential confusion. Quantum computers compute the same functions and Shor’s algorithm still factors in polynomial time. A single-tape Turing machine needs $\Theta(n^2)$ steps to do what a two-tape machine does in $O(n)$. The Church–Turing thesis is about computability; the extended Church–Turing thesis, which claims all reasonable models are polynomially equivalent, is a separate claim and quantum computing is widely believed to falsify it.

It does not say Turing-completeness is desirable. Most well-designed configuration and query languages deliberately stop short. SQL’s core relational algebra is not Turing-complete, which is exactly why a query planner can exist. eBPF verifies termination by rejecting unbounded loops. Coq and Agda are total by design, so a well-typed program provably terminates. Dhall, Starlark, and CUE all draw the line on purpose. Non-Turing-completeness is a feature you pay for and get analyzability in return, and Bitcoin Script’s deliberate lack of loops is a security property.

It does not say a Turing-complete system is practical. CSS with HTML is Turing-complete via Rule 110, and requires a user to click for each step. Magic: The Gathering is Turing-complete. These are real proofs of a mathematical property with zero engineering consequence, and treating “Turing-complete” as “powerful” is how the phrase gets misused. What actually matters for a config language is whether the analysis you want is decidable, which is a narrower question than completeness.

It does not rule out hypercomputation as mathematics. Oracle machines, infinite-time Turing machines, and Zeno machines are perfectly coherent mathematical objects and are studied seriously; the thesis claims only that none of them can be built. Relativized computation is a central tool in complexity theory (T030), and it does not threaten the thesis.

It does not depend on machines being deterministic or discrete-time. Gandy extended the analysis to parallel discrete machines, and the analysis survives. What it does need is discreteness: analog models with infinite-precision reals can compute non-computable functions, which is a statement about the physical plausibility of infinite precision rather than about computation.

Boundary

  • Physical Church–Turing. The strongest form claims that no physical process computes a non-computable function. This is a claim about physics, not mathematics, and is genuinely open — it is entangled with whether physical quantities are ultimately discrete and whether spacetime permits the relativistic supertasks (Malament–Hogarth spacetimes) that would allow infinitely many steps in finite proper time.
  • What would falsify it. A physically realizable device that decides halting. Nobody has any idea how to build one, and Gandy’s principles say which one you would need to break: unbounded information density in a bounded region. Bekenstein’s bound from physics says you cannot.
  • Total languages are the useful frontier. The interesting design space is not “complete or not” but how much you can compute while staying decidable. Primitive recursive functions, System F, and Coq’s terminating fragment cover effectively every program anyone writes, and give you termination for free.
  • The thesis is the load-bearing assumption of Part II. T010 and T011 prove things about Turing machines. That those results apply to your Python program, your CI pipeline, and any machine anyone builds is precisely what the thesis buys, and it is worth being conscious that it is an assumption.