Theory of computation

In the 1920s David Hilbert posed the *Entscheidungsproblem*: is there a mechanical procedure that can decide the truth of any mathematical statement? To answer it, someone first had to say precisely what "mechanical procedure" *means*. In 1936 two people did, in two guises. Alonzo Church built the lambda calculus, a spare formalism of functions applied to functions. Alan Turing imagined a machine — an idealized device scanning a tape of symbols, reading and writing by a fixed table of rules — and defined a number as computable if such a machine could churn out its digits. The two definitions proved exactly equivalent, and both delivered the same verdict to Hilbert: no. No universal decision procedure exists.

This drew a hard, permanent boundary around computation — before a single electronic computer had been built. Some precisely stated problems are *undecidable*: no algorithm settles all their cases, ever, no matter how fast the machine or how vast its memory. The halting problem is the emblem of this. And the Church–Turing thesis — that anything effectively computable by any means is computable by a Turing machine — means these are not the failings of some weak device but limits on mechanical computation as such. Knowing what *cannot* be computed is as foundational as knowing what can.

The stored-program computer is a physical universal machine — a real embodiment of the object Turing invented to prove an impossibility. From this root grew complexity theory, which asks not merely *whether* something can be computed but *how expensively* (the P versus NP question). Undecidability turns up everywhere once you look: in Gödel's incompleteness, in the impossibility of a general program that verifies other programs, in whole classes of unsolvable puzzles. Every compiler, interpreter, and operating system stands on the universal-machine idea that Turing found while proving where computation must stop.