On Computable Numbers, with an Application to the Entscheidungsproblem
Turing imagined the simplest possible machine — a head reading a tape — and used it to define computation itself, then proved there are questions no machine can ever answer.
Before any computer existed, Turing described the simplest machine that could compute anything at all — and used it to prove there are questions no computer will ever answer.
The idea, unpacked
Picture a long paper tape divided into squares, a little head that can read and write one square at a time, and a short rulebook. Each rule says: if you are in such-and-such a state and read such-and-such a symbol, write this, step left or right, and switch to that state. That is the whole machine. Turing's claim was startling: anything that can be calculated by a definite procedure can be done by a machine this simple.
Then came the masterstroke. The rulebook for any machine can itself be written out as symbols — so it can be written on a tape and fed to another machine. Turing built one “universal” machine that reads the description of any other machine and then behaves exactly like it. That is software: one device that becomes a word processor, a calculator, or a game, depending only on the description you load. He imagined it a decade before anyone built one.
Where it came from
In 1935 the 22-year-old Turing, a fellow at King's College, Cambridge, sat in on Max Newman's lectures on the open problems of mathematical logic. One was Hilbert's Entscheidungsproblem — the “decision problem” — which asked for a mechanical procedure that could decide, for any mathematical statement, whether it follows from the axioms. Turing took the word “mechanical” literally: to answer it, he first had to say exactly what a machine could do.
He finished the paper in 1936 — then learned that the American logician Alonzo Church had just reached the same conclusion by a completely different method. Turing's was independent and already at the press; he added an appendix proving the two approaches agreed, and soon left for Princeton to study with Church. The image at the heart of his proof — a human reduced to a tireless clerk following rules — would, within fifteen years, become the actual machine he had only imagined.
Why it mattered
It did two opposite things at once. It drew a sharp line under what machines can do — proving that some perfectly clear questions, like “will this program ever stop?”, have no general mechanical answer, so the dream of fully automating mathematics was impossible. And in the very same stroke it described the universal machine: the proof that one general-purpose device could, in principle, run any program at all. Every computer is a realisation of that single idea; the limits and the powers were discovered together, in the same paper.
An analogy
Imagine a clerk at a desk with an endless strip of paper and a thin rulebook. He doesn't understand the problem; he just reads the square in front of him, looks up the matching rule, writes, shuffles one square along, and repeats. Now notice: the rulebook is just writing too. So you could hand the clerk a description of any other clerk's rulebook and ask him to imitate it — one clerk who can stand in for all of them. The unanswerable question is simply: “Given a clerk and his starting page, will he ever put down his pencil?” No rulebook can always tell. Try the tiny machine below — it stops after 14 steps, but its cousins may run forever.
Where it sits
This is the keystone of the Library's information story. George Boole (1854) had turned logic into algebra; Kurt Gödel (1931) had shown that no formal system can prove every truth about arithmetic — and Turing's machine recast that limit in terms anyone can picture. His universal machine is the blueprint von Neumann's 1945 report turned into real hardware, and the bit it shuffles is what Shannon (1948) learned to measure. Fourteen years on, Turing's own 1950 paper asks the sequel: not what these machines cannot do, but whether they could ever think.
Opening — the computable numbers
The “computable” numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.
§1–§2 — Computing machines
§6 — The universal computing machine
It is possible to invent a single machine which can be used to compute any computable sequence.
§11 — The Entscheidungsproblem
There can be no general process for determining whether a given formula U of the functional calculus K is provable.