Turing's 'On Computable Numbers' (1936): The Universal Machine

In 1936 the 24-year-old British mathematician Alan Turing published “On Computable Numbers, with an Application to the Entscheidungsproblem”, one of the most influential papers in the history of science. In it he imagined a simple machine that could carry out any step-by-step calculation, used it to prove that some mathematical problems can never be solved mechanically, and described a single “universal” machine able to perform the work of all others. The paper gave the world a precise definition of computation and the theoretical foundation of the modern computer.

Background: Hilbert’s challenge

In the early 20th century the German mathematician David Hilbert led an effort to place all of mathematics on secure logical foundations. He hoped to show that mathematics was complete, consistent and decidable. In 1928 he and Wilhelm Ackermann posed the Entscheidungsproblem (“decision problem”): is there a definite procedure that can decide, for any statement in formal logic, whether it can be proved?

In 1931 the Austrian logician Kurt Gödel dealt a blow to Hilbert’s programme with his incompleteness theorems, which showed that any consistent formal system rich enough to include arithmetic contains true statements it cannot prove. The decision problem, however, remained open, partly because no one had a precise definition of what a “definite procedure” or “mechanical method” actually was.

Turing’s approach

Alan Turing was born in London in 1912 and studied mathematics at King’s College, Cambridge, where he was elected a fellow in 1935. That spring he attended lectures by the topologist Max Newman on the foundations of mathematics, which introduced him to Hilbert’s decision problem.

Turing’s insight was to analyse what a human “computer”, in those days a person who did calculations, actually does when following rules with pencil and paper. Such a person looks at a few symbols at a time, writes or erases symbols, moves attention to another place and changes their state of mind according to fixed instructions. Turing reduced this to an idealised machine with:

• an unlimited tape divided into squares, each holding one symbol;
• a head that reads and writes one square at a time and moves left or right;
• a finite set of internal states, and a table of rules saying, for each state and symbol, what to write, where to move and which state to enter next.

He argued that anything a human could calculate by following explicit rules could be calculated by such a machine. A real number was “computable” if a machine could write out its digits one after another.

The universal machine and the limits of computation

Turing showed that the rule table of any machine could be encoded as a string of symbols. He then described a universal machine: given the coded description of any other machine on its tape, it could simulate that machine step by step. In modern terms, the program could be stored as data in the same memory the machine worked on. This is the essential principle of the general-purpose computer.

He also proved that some questions about machines cannot be answered by any machine. Using a self-referential argument related to Georg Cantor’s diagonal method, he showed there is no general procedure that can examine an arbitrary machine’s description and decide whether it will go on printing digits forever. A closely related result, later called the halting problem, became one of the best-known facts in computer science. From this, Turing deduced that the Entscheidungsproblem has no solution.

Turing showed that his machines could compute all the familiar numbers of mathematics, such as π, e and the roots of algebraic equations. Yet because machines can be listed one after another while the real numbers cannot, it follows that almost all real numbers are uncomputable: no machine could ever write out their digits.

Church and the Church–Turing thesis

Turing was not alone. In April 1936, shortly before Turing submitted his paper, the American logician Alonzo Church at Princeton published an answer to the decision problem using a different formal system, the lambda calculus. Turing’s paper, received by the London Mathematical Society on 28 May 1936 and published in late 1936, added an appendix showing that his notion of computability was equivalent to Church’s. The American logician Emil Post also independently described a similar model in 1936.

The idea that these equivalent definitions capture everything that can be effectively calculated is now called the Church–Turing thesis. It was Church who, reviewing the paper in 1937, coined the term “Turing machine”. Most logicians, including Gödel, found Turing’s analysis of a human calculator especially convincing. In September 1936 Turing went to Princeton to work with Church, completing a doctorate there in 1938.

Key people

• Alan Turing (1912–1954): mathematician whose paper founded the theory of computation; he later worked on wartime codebreaking and early computers.
• Alonzo Church (1903–1995): American logician who solved the decision problem independently and supervised Turing’s doctorate.
• David Hilbert (1862–1943): German mathematician who posed the decision problem.
• Max Newman (1897–1984): Cambridge mathematician whose lectures inspired the paper and who arranged its publication.
• Kurt Gödel (1906–1978): logician whose incompleteness theorems set the stage for Turing’s work.

Consequences and legacy

At first the paper was read mainly by logicians. During the Second World War Turing applied his mathematical skills to breaking German codes at Bletchley Park, where he played a leading role against the Enigma cipher. After the war the universal machine became a practical blueprint. Turing’s 1945–46 design for the Automatic Computing Engine at the National Physical Laboratory was one of the first detailed plans for a stored-program computer, and John von Neumann’s 1945 report on the EDVAC, which drew on similar ideas, shaped American designs.

In the United States, machines such as ENIAC showed what electronic calculation could do, and in June 1948 the Manchester “Baby” ran the first program stored in electronic memory. In 1950 Turing published “Computing Machinery and Intelligence”, which proposed the “imitation game”, now known as the Turing test, as a way to ask whether machines can think. Turing’s concept of computability remains the foundation of theoretical computer science, and its highest award, the Turing Award, has been given since 1966.

Turing died in 1954 at the age of 41, two years after being convicted for homosexual acts, which were then illegal in Britain. The British government apologised in 2009, he received a posthumous royal pardon in 2013, and in 2021 his portrait appeared on the Bank of England’s £50 note, which reproduces a formula from his 1936 paper.

Timeline

• 1928: Hilbert and Ackermann pose the Entscheidungsproblem.
• 1931: Gödel publishes his incompleteness theorems.
• 1935, spring: Turing attends Max Newman’s lectures on the foundations of mathematics.
• 1936, April: Alonzo Church publishes his negative answer to the decision problem.
• 1936, 28 May: “On Computable Numbers” is received by the London Mathematical Society.
• 1936, November–December: The paper is published in the Society’s Proceedings.
• 1937: Church’s review coins the term “Turing machine”.
• 1948, 21 June: The Manchester Baby runs the first stored program.

Why it matters

“On Computable Numbers” answered a deep question in logic and, almost incidentally, described the general-purpose computer before one existed. Every modern computer, from smartphones to supercomputers, is in principle a universal Turing machine, and Turing’s proof that some problems can never be solved by computation still marks the outer limits of what computers can do.