The limits of computation

Context

The last demand standing. Gödel's 1931 theorems killed two-thirds of Hilbert's program — completeness and provable consistency — but the third demand, the Entscheidungsproblem, survived: is there a mechanical procedure that decides, for any mathematical statement, whether it is provable? To kill that, someone first had to say precisely what "mechanical procedure" means. Nobody had ever needed to. In spring 1935, in M.H.A. Newman's Cambridge lectures on the foundations of mathematics, a 22-year-old named Alan Turing heard the problem posed with Newman's phrasing — could there be a machine that settles it? — and took the word literally.

The machine. Turing's answer, worked out largely alone and delivered in 1936 as "On Computable Numbers," is one of the strangest and most consequential papers ever written: to prove a negative about all possible procedures, he first had to invent the computer — an idealized machine reading and writing symbols on an infinite tape, modeled on a human clerk with paper and pencil. Then two moves: a universal machine that can simulate any other machine from its description (software, before hardware existed), and Cantor's diagonal turned loose on it — feed a would-be halting-decider its own description, and it must contradict itself. The halting problem is undecidable; the Entscheidungsproblem falls; Hilbert's dream is dead on all three counts.

The race he lost, and won. As the paper neared completion, news arrived from Princeton: Alonzo Church had proved the same result months earlier using his lambda calculus. A devastated Turing added an appendix proving the two definitions equivalent — and that equivalence turned out to be the deeper discovery. Every reasonable formalization of "computable" (Turing machines, lambda calculus, Gödel's recursive functions) picks out the same class: the Church–Turing thesis, the claim that this class is what computation is. Turing went to Princeton to study under Church; von Neumann, who was there, later carried the universal-machine idea into the design of actual stored-program computers. The paper about what machines can never do became the blueprint for every machine since.

The question that remains. Decades later a different wall appeared behind this one: of the problems machines can solve, which can they solve before the sun burns out? That is tractability and P vs NP — computable-in-principle versus computable-in-practice — and it is still open. And Kolmogorov, Solomonoff, and Chaitin would rebuild information theory on top of Turing's machines: algorithmic information, where the undecidability proved here returns as the uncomputability of compression itself.

How to read it

Anchor. Moore & Mertens, The Nature of Computation. 900 pages, the one real textbook here. Read selectively: chapters 1–7 are the core (definitions, problem-solving, P vs NP, NP-completeness, randomness, cryptography, undecidability). Do some exercises or you won't internalize it. ~25 hours for the core chapters.

Companion. Petzold, The Annotated Turing — a guided walk through Turing's actual 1936 paper, with enough context that a careful reader can follow it. Read alongside or right after Gödel's Proof. ~15 hours.

Companion (optional). Sipser, Introduction to the Theory of Computation — the more formal alternative to Moore & Mertens. Use it if you want theorem-proof rigor; most readers won't need both.

Companion (philosophical). Chaitin's short essays on algorithmic information theory. Eccentric but clarifying.

The connection to hold onto: computation and formal systems are two faces of the same limit.