The History of AI

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.

The machine reads a square, looks up its table of rules for the state it is in, writes, moves, and changes state.

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

Three definitions of mechanical calculation (1936)
FeatureChurchTuringPost
ModelFunctions of the lambda calculusMachine with a tape, a head, and statesA worker who marks boxes
PublicationAmerican Journal of Mathematics, AprilProceedings of the London Mathematical Society, November and DecemberJournal of Symbolic Logic, September
PlacePrincetonCambridgeNew York
Answer to the decision problemNo solutionNo solutionNot 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

Sources

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.

Open in the interactive timeline