May 28, 1936

Turing machine

Turing submits "On Computable Numbers" to the London Mathematical Society

The paper that defined a universal computing machine arrived before any programmable electronic computer existed — its tape was an abstraction of paper.

28 May 1936: received by the London Mathematical Society

The London Mathematical Society received Alan M. Turing's manuscript 'On Computable Numbers, with an Application to the Entscheidungsproblem' on 28 May 1936. Turing was 23.

The journal's copy still prints the bureaucratic trail: received 28 May, read 12 November.

A machine made of finitely many states

The manuscript introduced an abstract model of computation — a machine with finitely many states, a symbol-bearing tape, and a scanning head that could read, write, erase and move one square at a time. It defined computable numbers through machine procedures and described a universal machine capable of simulating encoded machines.

Turing then used undecidable machine problems to show that David Hilbert's Entscheidungsproblem — the search for a general mechanical decision procedure for formal logic — has no such solution.

What the paper did and did not prove

Attributing the modern halting problem to this paper is contested. Turing proved the undecidability of his circle-free and symbol-printing problems, which are related to but not identical with the modern input-and-halting formulation; for his successful number-computing machines, running forever was correct behaviour, since the machine had to keep printing digits.

Alonzo Church had independently reached an equivalent undecidability result using lambda calculus, and Turing added discussion of Church's work after learning of it. Submission was not publication: the paper was read on 12 November and appeared in two installments, on 23 November and 23 December 1936.

Sources

Researched 23 Aug 2026 5 sources 3 audit passes

How this was checked

Researched from the web into a fact sheet, rewritten from that sheet, then audited against it by a different model. How the pipeline works →

What the sources leave uncertain

The receipt date is printed on the paper itself and is secure.
Attributing the modern halting problem itself to this paper is contested. Turing proved the undecidability of his circle-free and symbol-printing problems; these are related to, but not identical with, the modern input-and-halting formulation.