Part VI — Chapter 20
Gödel & Turing — Limits of Computation
The boundaries of what mathematics and machines can know
20.1 Gödel's Incompleteness Theorems
In 1931, Kurt Gödel (1906–1978) proved that any consistent formal system powerful enough to express arithmetic must contain true but unprovable statements — and cannot prove its own consistency. These results destroyed Hilbert's program.
20.2 Turing Machines
Alan Turing (1912–1954) formalized computation through abstract Turing machines and proved the halting problem undecidable. His universal Turing machine became the theoretical foundation for modern computers. During WWII, he broke the Enigma code at Bletchley Park.