01 · Theory of Computation

This chapter is the bedrock of the tower — the floor that decides what every floor above it is permitted to attempt.

What can be computed at all — and what never, on any hardware?

Here is a tool every working programmer would like to own. It reads a program and its input and answers one question: will this finish, or will it run forever? No more hung builds, no more servers looping overnight. It need not even fix the program, only report on it.

It cannot exist. Not "nobody has managed it yet," not "it would be too slow" — no such program can be written, on any machine ever built or ever to be built, and the proof was published in 1936, before there was a machine to run it on. Why is the whole of this floor, and the reason the floor sits at the bottom of the tower: it fences the territory everything above builds on.

The question came from Hilbert, and was meant to have a happy answer. In 1928 David Hilbert and Wilhelm Ackermann published Grundzüge der theoretischen Logik, the first textbook exposition of first-order logic, and posed in it the Entscheidungsproblem: is there a definite procedure that takes any statement of logic and decides whether it follows from the axioms (Springer)? Hilbert expected there was. In Königsberg on 8 September 1930 he closed a speech with the line later carved on his gravestone: Wir müssen wissen — wir werden wissen — we must know, we will know (MAA Convergence).

The day before, at a roundtable closing a conference in the same city, a young logician named Kurt Gödel had mentioned almost in passing that any consistent formal system strong enough to describe arithmetic must contain true statements it cannot prove. The room let it go by; John von Neumann, present, appears to have been the only person who grasped what had happened (Davis, Notices of the AMS, 2006). The paper followed in 1931 (Monatshefte für Mathematik und Physik 38: 173–198).

Gödel had holed the ship, but the Entscheidungsproblem stayed afloat: you cannot prove no procedure exists until you have said what a procedure is.

The definition was found by watching a person. Alan Turing's move, at twenty-three and a Fellow of King's College, was less mathematical than anthropological. In 1936 a computer was a job title: a human being, usually poorly paid, who calculated. Turing watched one. "Computing is normally done by writing certain symbols on paper," he wrote. "We may suppose this paper is divided into squares like a child's arithmetic book" (On Computable Numbers, §9). Then he stripped the human away one faculty at a time: a bound on the symbols taken in at a glance, a bound on the "states of mind" he can hold, nothing to do but look, write, and move. What remains is a tape, a finite table of rules, and a head that reads and writes — the Turing machine, less a machine than a description of what a person does when they stop thinking and start following instructions. The London Mathematical Society received it on 28 May 1936.

Everyone who defined it independently landed in the same place. Alonzo Church got there first by another road: an April 1936 proof, built on his lambda calculus, that no such procedure exists (American Journal of Mathematics 58: 345–363). Emil Post reached a near-identical formalism that year; Gödel and Kleene, general recursive functions. All define exactly the same class, and that convergence is the evidence for the Church–Turing thesis: this class is what we informally mean by "effectively calculable." It is a thesis, not a theorem, and cannot be otherwise: it joins an informal human idea to a formal object, and no proof bridges that gap (Stanford Encyclopedia of Philosophy). It is also why this floor's results are hardware-proof: build a computer from anything you like — tubes, silicon, qubits — and if it computes at all, it computes this set and no more.

One machine can be all machines. Section 6 of Turing's paper opens with the most consequential sentence in it: "It is possible to invent a single machine which can be used to compute any computable sequence." Hand a machine the description of another and it behaves as that one. Before this, a calculating device was built for its task — a loom for weaving, a differential analyzer for equations. After, the machine is blank and the task arrives as data. Everything downstream depends on that: software separable from hardware, the compiler, the emulator, the virtual machine, the operating system running programs it was never designed for. Universality is the hinge the tower swings on.

And some questions simply have no procedure. The proof is Cantor's diagonal argument of 1891, turned on machines. Suppose the halting checker exists. Build a program that hands the checker its own description and does the opposite of the prediction: halt if told it loops, loop if told it halts. Ask the checker about that program and it must be wrong. So it never existed.

Two footnotes of honesty. Turing used neither that name nor that proof; he proved undecidability for related problems about his machines, and both name and modern formulation appear later, in Martin Davis's Computability and Unsolvability of 1958 (Hamkins & Nenu, 2024). And halting is no exotic special case: H. G. Rice proved in 1953 that every non-trivial question about what a program computes is undecidable (Transactions of the American Mathematical Society 74: 358–366). That is a fence, not a pothole — why no compiler will promise your loop terminates, why no antivirus can decide by analysis alone whether a program is malicious, and why every static analyzer answers "yes," "no," or "I cannot tell." That third answer is a theorem, not a bug.

Past the wall of the possible stands a second wall: the affordable. A problem can be decidable and still cost more than the universe can pay. Stephen Cook showed in 1971 that Boolean satisfiability is NP-complete, and Leonid Levin proved as much independently in 1973 (Cook's own account). The instrument behind such a claim is reduction: a translation cheap enough that a fast solver for one problem becomes a fast solver for another — one hard problem made into a lever on all the rest. In 1972 Richard Karp used it to show that twenty more natural problems were the same problem in disguise (Karp, 1972); by 1979 Garey and Johnson's Computers and Intractability catalogued three hundred. Whether checking an answer quickly implies finding one quickly — P versus NP — was posed in a letter Gödel wrote to the dying von Neumann on 20 March 1956 (translation), carries a million-dollar Clay Institute prize, and is unsolved (CMI). The wall leaks usefully, though: the best proven bound for 3-SAT is exponential, yet industrial solvers routinely dispatch structured instances of over a million variables (Gomes et al.). Worst case is not typical case — where the next floor begins.

Connections

Below: 00, the map. Above: 02, which takes every problem this floor calls possible and asks what it costs, turning the same counting arguments into lower bounds. Universality is what 05 sells as virtualization and 06 as compilation. 11 builds on the second wall: cryptography is the deliberate manufacture of problems believed unaffordable.

Open questions

P versus NP, obviously — though a proof that P = NP would be less a theorem than an event: the security of the internet dissolved, much of mathematics handed to a machine. Is the thesis itself safe? Quantum computers compute nothing a Turing machine cannot, but may break its efficiency version — chapter 14's territory. And the deepest: undecidability limits machines and, through the thesis, any procedure a human could follow. Does anything escape it, or is the fence around the possible simply the shape of thought?

Go deeper

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2012 — the standard course text (author's page).
• A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem," Proceedings of the London Mathematical Society, ser. 2, 42 (1936–37): 230–265 — worth reading for §9 alone (PDF).
• Richard Karp, "Reducibility Among Combinatorial Problems," 1972 — the paper that turned NP-completeness from a theorem into a map (PDF).