On Computable Numbers, with an Application to the Entscheidungsproblem

Alan Turing's paper "On Computable Numbers, with an Application to the Entscheidungsproblem" was received by the London Mathematical Society on 28 May 1936 and read there on 12 November of that year. It was published in the society's Proceedings, Series 2, Volume 42, pages 230 to 265, and a correction followed in Volume 43 in 1937.^[1] According to the Stanford Encyclopedia of Philosophy, the work was about a year of solitary effort by Turing, then a 23-year-old Fellow of King's College, Cambridge, and it was completed in April 1936.^[2] The paper is long and technical, but its central idea is easy to state: it gives a precise definition of what a machine can compute.

The problem

The title names the target. Hilbert's Entscheidungsproblem (decision problem) asked for a general method that decides, for any given mathematical statement, whether it can be proved. Answering that question first required a precise meaning for "mechanical." Turing started with a class of real numbers, those whose decimal expansions can be written down by a machine, and called them computable numbers.^[1]

The method

The machine Turing described is an abstract device, not a piece of hardware. It has a finite number of states, which he called m-configurations, and it reads and writes symbols on a tape divided into squares. At each step, the machine's current state together with the symbol under its reading head determines what it writes, which way it moves, and which state it enters next. This device is now called the Turing machine.^[1]

Its power comes from its simplicity. A machine with only a few states can be designed to print a repeating pattern such as 0, 1, 0, 1 along its tape, and a more elaborate machine can carry out a longer calculation one small step at a time. Turing's central claim was that any calculation carried out by following fixed rules can be described in this way.^[1]

The most important step comes in Section 6, "The universal computing machine." Turing showed that one machine can compute any computable sequence if the tape also carries a description of the machine to be imitated. In modern terms, this is the idea of a universal, programmable computer: the same machine, loaded with different programs, can do different jobs.^[1]

The results

Using a diagonal argument, Turing showed two things. The computable numbers, although a very large class, can be listed one after another in order. And some definable numbers are not computable at all.^[1]

The main application, in Section 11, concerns the Entscheidungsproblem. Turing showed that it can have no solution: no single mechanical method can decide, for every mathematical statement, whether it is provable.^[1]

Turing was not working alone on the question. Alonzo Church had just introduced an equivalent notion, which he called "effective calculability," and had reached similar conclusions about the Entscheidungsproblem. Turing noted this, and an appendix added on 28 August 1936 outlines a proof that the two notions are equivalent.^[1]

Why it mattered

Turing's definition gave an exact answer to the question of what a machine can compute, and that answer has since become one of the foundations of computer science.^[2] It also reached beyond mathematics. Turing's own 1950 paper, "Computing Machinery and Intelligence," took up whether machines can think, and arguments of that kind rest on the same precise idea of computation.^[2]

In recognition of this 1936 achievement, Turing was elected a Fellow of the Royal Society in 1951.^[2]

What followed

The ideas introduced here remain the usual starting point for reasoning about what computers can and cannot do. The universal machine underlies the general-purpose, programmable computer. The undecidable question underlies many later results showing that some problems cannot be solved by any program in general. For anyone studying the theory of computing, this paper is a natural place to start.