On Computable Numbers, with an Application to the Entscheidungsproblem

Turing argues that the intuitive notion of a 'computable' number can be captured precisely by an automatic machine—a finite-state device operating on an infinite tape according to a fixed table of instructions. The paper rejects the assumption that the Entscheidungsproblem must await a definitive formal definition of 'algorithm' from logic alone. By constructing his machines from an analysis of what a human computer actually does when following a rule, Turing provides an absolute definition of computability and then uses it to prove that no machine can decide, for every formula of first-order logic, whether it is valid. The result is a negative solution to Hilbert's decision problem, achieved through a positive and enduring model of computation .

The universal machine is a single automatic machine that can simulate the behaviour of any other automatic machine when supplied with a description of that machine's instruction table on its tape. Turing's construction showed that universality—the capacity of one machine to do the work of all others—is a mathematical property of certain instruction tables, not a physical accident. This insight is the conceptual basis of the stored-program computer: data and instructions can be encoded in the same medium. As Andrew Hodges notes, Turing's unification of data and instructions on a single tape was the theoretical insight that later informed his work on the ACE and the design of general-purpose electronic computers . The universal machine transformed computability from a property of particular devices into a property of a single abstract structure.

Turing's proof is structurally analogous to Gödel's but methodologically distinct. Gödel showed that any sufficiently powerful formal system contains undecidable propositions by arithmetizing syntax and constructing a self-referential sentence. Turing showed that no automatic machine can decide, for an arbitrary machine and input, whether that machine will ever halt, by a diagonal argument operating on machine descriptions. The two results are independent but convergent: both establish limits on formal decidability. Importantly, Turing's proof convinced Gödel that the Turing machine offered the most natural absolute definition of computability. As Gödel reportedly said, Turing's concept achieved 'for the first time' an absolute definition of an epistemological notion 'not depending on the formalism chosen' . The paper thus both extends and, in a sense, completes the Gödelian project.

The paper was published in 1936 and immediately impressed logicians, including Church and Gödel, who recognized Turing's analysis as more intuitively compelling than Church's lambda calculus. Turing's proof of the unsolvability of the Entscheidungsproblem was accepted as a simpler and clearer alternative to Church's . However, the paper's impact on the emerging computer-building community was negligible in the 1930s and 1940s. Hodges notes that Turing's paper 'had little impact on the computer-building community at large' during this period . Its transformation into a foundational text of computer science occurred in the 1960s, when theoretical computer scientists adopted the Turing machine as the standard model of computation. The universal machine, initially a mathematical device for a logical proof, became the conceptual ancestor of the general-purpose computer.

Turing published a correction to the paper in 1937, in volume 43 of the Proceedings of the London Mathematical Society . The correction addressed a technical error in Turing's original treatment of the diagonal argument, specifically concerning the definition of the machine that is supposed to decide the halting problem. The correction does not alter the paper's main results; it tightens the proof of the undecidability of the Entscheidungsproblem. The existence of the correction is sometimes overlooked, but it is part of the paper's textual history and should be consulted by readers working through the details of Turing's argument. The archive at King's College Cambridge holds extracts of both the original paper and the correction .

The Turing thesis, often conflated with the Church-Turing thesis, is the claim that any function that can be computed by an effective procedure—by a human following a finite set of unambiguous rules—can be computed by a Turing machine. Turing argues for this thesis by analyzing what a human computer actually does: reading symbols, writing symbols, and changing state according to a finite table. He then shows that any such process can be simulated by an automatic machine. The thesis is not a theorem that can be proved, because it equates an informal notion (effective computability) with a formal one (Turing computability). As the literature notes, the equivalence 'cannot be proved and needs to be accepted or rejected on grounds that are largely empirical' . The paper's analysis of the human computer is what gives the thesis its philosophical weight.

Church had already published a negative solution to the Entscheidungsproblem in 1935, using the lambda calculus as his definition of effective computability. Turing was unaware of Church's work when he completed his paper. Turing's approach differs in its starting point: Church began from a formalism and argued for its adequacy, while Turing began from an analysis of the concrete activity of a human computer and derived the formalism from it. This is why Gödel found Turing's definition more convincing than Church's. Turing later proved that the lambda calculus and automatic machines define the same class of functions, establishing the equivalence that grounds the Church-Turing thesis. The paper thus revises and, in a sense, completes Church's result by providing a more intuitively grounded foundation for computability.

A common misreading treats the paper as a contribution to engineering or as the design specification for a physical computer. Turing's machines are abstractions, defined by instruction tables and an infinite tape; the paper is a work of mathematical logic, not a blueprint for hardware. The universal machine is a mathematical construction, not a proposed device. The confusion arises because the universal machine later became the conceptual model for the stored-program computer, and Turing himself went on to design real machines during and after the war. But the 1936 paper's aim is to solve a problem in the foundations of mathematics: whether a decision procedure exists for first-order logic. Reading it as an engineering document misses its negative result and its methodological innovation.