Computability · 1936 · Alan M. Turing
On Computable Numbers, with an Application to the Entscheidungsproblem
Replace the vague idea of a mechanical procedure with an explicit machine, encode machines as data, and use diagonalization to prove that some questions are undecidable.
The central move
Replace the vague idea of a mechanical procedure with an explicit machine, encode machines as data, and use diagonalization to prove that some questions are undecidable.
Why it had to exist
Hilbert’s decision problem asked whether a mechanical method could decide every mathematical statement. Before answering, Turing had to say exactly what mechanical method meant without defining it as whatever a real machine happened to do.
Where it leads
Formal procedure → universal machine → stored programs → interpreters, compilers, and the hard limits beneath every general-purpose computer.