On Computable Numbers
Era 1 · The foundations (1763–1942) › Computability
- Lineage
- Symbols and logic
- Kind
- Publication
Who
King's College, Cambridge
What happened
Alan Turing, 24, publishes "On Computable Numbers, with an Application to the Entscheidungsproblem" in the Proceedings of the London Mathematical Society, in two parts dated November 30 and December 23, 1936.
Why it mattered
The Turing machine, and the universal machine that runs any other machine from its description: the theoretical model of the stored-program computer. It reaches Church's result by a different route.
The full story
Alan Turing was 22 when, in 1935, in Cambridge, Max Newman's lectures on the foundations of mathematics described the decision problem as the search for a "mechanical process." Turing took the phrase literally and asked what, exactly, a person does when calculating by following rules.
The answer is an imaginary machine. It reads and writes symbols on a tape divided into squares, one at a time, and at each step decides what to write, which way to move, and which state to enter next, based on the symbol it sees and its current state. Turing argued that any calculation a person can do with pencil and paper can be done by one of these machines. Then came something more surprising: a single machine, the universal one, can imitate any other if it is given that other machine's description on its tape. Program and data are the same kind of thing.
With this model Turing proved that no machine can decide, for every other machine, whether it will go on printing digits forever, and from this that Hilbert's decision problem has no solution. Today the result is taught as the halting problem, a name Martin Davis gave it in the 1950s. While preparing the paper, Turing learned that Church had reached the same conclusion with the lambda calculus, and added an appendix proving that the two definitions are equivalent.
That fall, in New York, Emil Post independently published an almost identical model. In a 1937 review, Church called Turing's model a "Turing machine." Turing spent 1936 to 1938 at Princeton, studying under Church. The universal machine, which keeps program and data on the same tape, is the theoretical model of the stored-program computer.
A row of squares holding zeros and ones; beneath one of them, a head in state q₁; below, a sample rule from the table.
Under the hood
A Turing machine has a tape divided into squares, a head that reads one square at a time, and a finite number of states. Its table says, for each state and each symbol read, what to write, whether to move left or right, and which state to go to.
The universal machine receives another machine's table on its tape, written as a string of symbols, and imitates it step by step. To prove that the decision problem has no solution, Turing assumes there is a machine that can decide whether any other machine behaves well and uses it to build a machine that contradicts itself: a diagonal argument like Cantor's.
Side by side
| Feature | Church | Turing | Post |
|---|---|---|---|
| Model | Functions of the lambda calculus | Machine with a tape, a head, and states | A worker who marks boxes |
| Publication | American Journal of Mathematics, April | Proceedings of the London Mathematical Society, November and December | Journal of Symbolic Logic, September |
| Place | Princeton | Cambridge | New York |
| Answer to the decision problem | No solution | No solution | Not addressed in the paper |
Common misconceptions
What people often say: The Turing machine is a device Turing built.
In fact: It is a mathematical model, an imaginary machine for defining what it means to compute. Turing never built one, although real computers designed by Turing came later, such as the ACE.
Videos
Builds on
The Entscheidungsproblem (1928)
Documented direct influence
Both papers answer the Entscheidungsproblem; Turing's names it in its title
The lambda calculus and an unsolvable problem (April 1936)
Independent convergence
The same result, reached independently
The incompleteness theorems (1931)
Documented direct influence
Turing compares the paper's result with Gödel's theorem and explains how it differs (section 8)
Finite Combinatory Processes (September 1936)
Independent convergence
Two almost identical models of mechanical computation, written separately; a note in Post's paper invites comparison with Turing's and makes clear it was written independently
Leads to
The McCulloch-Pitts neuron (December 1943)
Documented direct influence
The paper argues that a net with a tape and the means to read and write it computes the same things as a Turing machine
Threads that pass through here
- From Hilbert's question to the universal machine (step 7 of 7)
Sources
Original source
- On Computable Numbers, with an Application to the Entscheidungsproblem (Proceedings of the London Mathematical Society, series 2, vol. 42, pp. 230-265) (opens in a new tab). Alan M. Turing, 1936
- Finite Combinatory Processes. Formulation 1 (The Journal of Symbolic Logic, vol. 1, no. 3, pp. 103-105) (opens in a new tab). Emil L. Post, 1936
Scholarship and context
How to cite
“On Computable Numbers.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/turing-on-computable-numbers
This entry was last reviewed on November 13, 2026.