Turing Machines & the Halting Problem
Alan Turing · 1936
"Turing proved that no general algorithm can decide in advance whether an arbitrary program will ever halt — some questions are not just hard, they are uncomputable, which sets a hard limit on what automation can ever guarantee."
In 1936 a 24-year-old at Cambridge asked a disarmingly simple question: can we build a machine that looks at any program and tells us, beforehand, whether it will ever finish running? His answer — no — is the most important negative result in computer science.
Turing formalized computation as a simple machine reading and writing symbols on a tape, then showed that a hypothetical 'halting decider' leads to a logical contradiction — a program that halts exactly when the decider says it doesn't. The diagonal argument mirrors Gödel's, but for code: the limits are not in how fast we compute, but in what can be computed at all. Modern implications run from why perfect virus detectors are impossible to why AI safety can't be reduced to 'just check the output before running it.'
What does Turing's halting problem actually prove?
Read more about the topic
The explanation above is written with AI assistance. These are the originals — go to them to check it.
- On Computable Numbers, with an Application to the Entscheidungsproblem (1936)Proceedings of the London Mathematical Society
- Turing MachinesStanford Encyclopedia of Philosophy (B. Jack Copeland)
Russell's Paradox & the Foundations Crisis
"Russell showed that naive set theory lets you define 'the set of all sets that don't contain themselves,' which both contains and doesn't contain itself — forcing mathematics to rebuild its foundations with stricter rules."