CS PAPERS DEEP-READ · PAPER 42
Alan Turing · King's College, Cambridge · 1936 (Proc. London Math. Soc., 1937)
Every day you open your phone, and the same chip becomes a camera, then a map, then a chat box — one machine that turns into any machine when you load a different "instruction sheet." Engineers didn't think of that first. A 24-year-old mathematician, Alan Turing, worked it out in 1936 in a pure-math paper. Setting out to answer an abstract question, he pinned down exactly what "to compute" means — and sketched the blueprint for every computer that would ever exist.
The towering mathematician David Hilbert had posed an ambitious challenge: is there some rote procedure that takes any mathematical statement, and mechanically grinds out "true" or "false"? If so, mathematicians could retire. But to answer "is there such a procedure?", you first hit a deeper snag: what does "a rote procedure" even mean? Before Turing, "rote," "mechanical," "by the book" were pure intuition — nobody had made them precise.
Turing didn't strain for a grand definition. He watched how a real person computes with pencil and paper, then stripped it to the bone: an endless tape of squares holding symbols; a pencil tip that looks at one square at a time; a handful of states of mind ("carrying a digit"); and a rigid lookup table — "in this state, seeing this symbol: rewrite the square, move the tip one step, switch state." Do that over and over, and that's "computing." This imagined device is the Turing machine. It's almost laughably simple, yet it can compute exactly as much as today's mightiest supercomputer.
Here comes the staggering step. Since every Turing machine's lookup table is just a string of symbols, write that table onto the tape too, and read it as data. Turing built one special machine: put "the instruction sheet of some machine M" on its tape, let it read, and it will impersonate M and do everything M does. He called it the universal machine. This is the birth of "software" — a program is no longer hard-wired circuitry, but a piece of data you can read and swap out. The computer in your hand is, at heart, this universal machine.
Then Turing drew a hard boundary around this all-powerful device. He asked: could there be a machine that glances at another's instruction sheet and decides whether it will run forever or eventually jam? He proved no — by making a machine sit in judgment over itself, like the sentence "this sentence is false" that spins out the moment it turns on itself. So back to Hilbert's grand question: that universal deciding procedure simply does not exist. Mathematics always holds corners no machine can reach — not because machines are too slow, but because logic forbids it. That boundary has never been crossed.
To answer "is there a universal procedure that decides everything," Turing first defined "computing" as a minimal tape machine, then invented the universal machine that "reads an instruction sheet and becomes any machine" (the blueprint of every computer), then proved that some questions no machine can ever decide — so the universal procedure doesn't exist. One pure-math paper laid both the foundation of computers and their ceiling.
Want the machine diagram, the universal machine, and how the diagonal argument corners a machine into contradicting itself? → switch to the deep read
To answer Hilbert's Entscheidungsproblem (decision problem), Turing gave the first convincing precise definition of "mechanical computation" — the Turing machine — and from it drew three things: encode every machine as data and build a universal machine that simulates any machine (the blueprint of the stored-program computer); prove by a diagonal argument that some problems no machine can decide; and hence prove the decision problem has no solution — first-order logic has no universal deciding algorithm. The paper founded both "what an algorithm is" and "what algorithms cannot do."
The author, Alan Turing, was a 24-year-old fellow at King's College, Cambridge; the paper was submitted in 1936 and published in 1937 in the Proceedings of the London Mathematical Society. It answers the decision problem of Hilbert and Ackermann (1928), standing on the shoulders of Gödel's incompleteness theorems (1931). Almost simultaneously, Alonzo Church at Princeton reached the same negative result independently (a few months earlier) using the lambda calculus. Turing then went to Princeton as Church's student, and in an appendix proved his own "machine-computable" is the same notion as Church's "lambda-definable." Downstream lies all of computer science — the von Neumann architecture, computability theory, complexity theory all trace back here.
Early in the 20th century, Hilbert dreamed of packing all of mathematics into one formal system, plus a "deciding machine": feed in any statement, grind mechanically, and learn whether it's true and provable. In 1931 Gödel proved that any sufficiently strong system contains true-but-unprovable statements, shattering the "complete" half of that dream. But one question remained — the decision problem: even if the system is incomplete, is there a mechanical procedure that can at least decide whether a statement is logically valid?
To answer "is there such a procedure," you must first answer a subtler prior question: what is a "mechanical procedure"? As long as "algorithm" stayed at "follow the rules by intuition," you could never prove that something is beyond every algorithm — because you'd never pinned down what "every algorithm" means. That was the wall everyone hit. Turing's breakthrough was to define "computation" itself first, so the question could, for the first time, be proved.
Turing's starting point is startlingly plain: watch how a person (back then, a human doing computation was literally called a "computer") works with pencil and paper, then strip away everything but the bare essentials. His insight was that at any instant a person really depends on only finitely much: the eyes fix on one small patch of paper, the mind holds a finite number of "states," and each move is one of finitely many kinds. Idealize these and you get a machine:
(current state, symbol read) → (write a symbol, move one square left or right, switch to a new state).The machine just keeps consulting this table. Why design it this way? Because it compresses "mechanical computation" to the irreducible: an endless tape = unlimited scratch paper; scanning one square at a time = human attention is finite; finite states + finite rules = "by the book, no inspiration." Anything computable by any well-defined algorithm can be translated into such a table. Conversely, the machine is simple enough to serve as the mathematical definition of "algorithm" itself.
The paper's literal goal is to define computable numbers: a real number is computable if its (binary) expansion can be printed out, digit by digit, by such a machine. π, e, and all algebraic numbers are computable. A machine that keeps printing forever without jamming, Turing calls circle-free.
The crucial leap: since each machine is just a finite table of behavior, you can write the whole thing as a string of symbols, then read it as an integer (Turing's "description number"). This bookkeeping trick is immensely powerful. It means all Turing machines can be numbered one by one: machine 1, machine 2, machine 3… — the machines are countable.
But the reals are uncountable (Cantor proved this long before). So a startling conclusion follows at once: the vast majority of real numbers are "uncomputable" — no algorithm generates their expansion. The computable numbers include every number we can name, yet they are only a countable sliver in the ocean of reals. That already punctures half the illusion that "machines can do anything."
Since every machine M can be written as data (its description number), Turing built a universal machine U: put "M's instruction sheet" plus M's input on U's tape, and U reads a bit, executes a step, reads more… simulating M step by step and computing exactly what M would. One machine, fed different instruction sheets, becomes any machine.
This is the mathematical prototype of the "stored program": a program is no longer a hard-wired special-purpose device, but a symbol string sitting on the same tape as the data, readable and replaceable. Every computer today — one piece of general hardware that becomes a camera, a browser, a game console by loading different software — is a physical realization of Turing's universal machine. A decade later, the von Neumann architecture turned it into real hardware.
With numberable machines and a universal machine in hand, Turing asks the fatal question: could there be a machine D that, just from another's description number, decides whether that machine is circle-free (will it keep computing forever, or eventually jam)? He proves no such D exists, using exactly Cantor's diagonal argument.
The intuition runs thus: suppose D exists. Then you could use it to list all the "good" machines (the circle-free ones), number them, and lay their infinite 0/1 outputs into a giant table — row n is the output of the n-th good machine. Now read down the diagonal and flip each digit to build a new sequence β: its n-th digit is deliberately different from the n-th machine's n-th digit. So β differs from every row in at least one place and cannot be any machine in the table. Yet — if D really exists, "building β" is itself an algorithm, so β should be computed by some good machine and be in the table. It is both in and not in the table: a contradiction. Hence D does not exist.
The root of the contradiction is self-reference: the "build the diagonal" machine is eventually asked to compute its own digit, and gets stuck in "output something different from itself" — the same knot as "this sentence is false." Conclusion: some problems no machine can decide. (Turing's original phrasing is that "circle-free-ness" is undecidable; the textbook version today is the equivalent halting problem: no algorithm can decide, for an arbitrary program and input, whether it halts or loops forever.)
The last step carries the machine undecidability onto logic. Turing shows any Turing machine's run can be translated into a single first-order logic statement — how the machine behaves is equivalent to whether that statement is valid. So if a universal algorithm for the decision problem existed (deciding validity of any logical statement), you could use it to decide "will the machine jam" — which was just proved undecidable. Contradiction. Therefore the decision problem has no solution: there is no mechanical procedure that decides all first-order logic statements. The last half of Hilbert's dream ends here.
This is a pure-math paper with no experiments; the "results" are a few interlocking theorems: ① the Turing machine gives a precise definition of "mechanically computable"; ② machines can be numbered one by one (countable), so the vast majority of reals are uncomputable; ③ a universal machine exists — one machine can simulate any machine; ④ "is a machine circle-free" is undecidable (the prototype of today's halting problem); ⑤ hence the decision problem has no solution. In an appendix he further proves "Turing-machine-computable" and Church's "lambda-definable" are exactly equivalent — two utterly different roads enclosing the same territory of "computable," a coincidence that is the evidence for the Church–Turing thesis.
Few computer-science papers are more foundational. It delivered three foundations at once: first, "algorithm / computable" acquired an agreed definition, giving theoretical computer science an object to study; second, the universal machine = the blueprint of the stored-program computer, the idea "program is data, one machine for all" leading straight to the von Neumann architecture and every computer today; third, undecidability drew computing's absolute boundary, spawning the halting problem, Rice's theorem, and a whole family of "what machines cannot do" results (no perfect general program verifier, no perfect antivirus). You could say that today's ability to load any software onto a single chip, and to prove some automation tasks impossible in principle, both root in these 36 pages. The Turing test and AI came later from Turing; the definition of computation itself was born here.
① In one line: to answer Hilbert's "is there a mechanical procedure that decides every mathematical statement," Turing first defined "computing" as a Turing machine, then proved that universal procedure doesn't exist.
② The pain: without first defining "algorithm / mechanical procedure," you cannot prove "no algorithm can do X" — which stalled the decision problem.
③ The Turing machine: endless tape + a head scanning one square + finite states + a rigid table, (state, read) → (write, move, new state) — the mathematical definition of "algorithm" itself.
④ Encoding: each machine can be written as a number and enumerated (countable); the reals are uncountable, so most reals are uncomputable.
⑤ Universal machine: read a "machine's instruction sheet" as data, and one machine simulates any machine — "program is data," the blueprint of the stored-program computer.
⑥ Undecidability: by a diagonal argument + self-reference, "is a machine circle-free (today's halting problem)" has no deciding algorithm.
⑦ Reduction: translate a machine's run into a logic statement to prove the decision problem unsolvable; an appendix proves equivalence to Church's lambda calculus (Church–Turing thesis).
⑧ Impact and limits: laid the foundations of the definition of algorithm, the universal-machine blueprint, and the boundary of computation; but the thesis is unprovable, the machine impractical, the original had errors, and it addresses feasibility only, not efficiency.