"On Computable Numbers, with an Application to the Entscheidungsproblem" is a seminal 1936 paper by Alan Turing. It introduces the concept of a universal computing machine (later called the Turing machine) as a formal model of computation. The paper defines computable numbers as those whose decimal expansions can be produced by a finite mechanical process, and uses this framework to prove that the Entscheidungsproblem (decision problem) posed by David Hilbert is unsolvable—i.e., there is no general algorithm that can determine the truth or falsity of all mathematical statements. This work laid the foundation for computability theory and modern computer science.
1 Historical Context
The early twentieth century witnessed a profound crisis in the foundations of mathematics. Efforts to place all of mathematics on a secure, axiomatic basis culminated in David Hilbert’s formalist program, which sought to prove the consistency and completeness of mathematical systems. Central to this program was the *Entscheidungsproblem*, the decision problem for first-order logic. Turing’s paper provided a definitive negative answer to this problem, thereby reshaping the landscape of logic and computation.
1.1 Hilbert’s Entscheidungsproblem
In 1928, David Hilbert and Wilhelm Ackermann posed the Entscheidungsproblem: find a mechanical procedure (algorithm) that, given a statement in first-order logic, determines whether it is universally valid (i.e., true in all interpretations). Hilbert believed such a procedure might exist, and that its existence would underpin the decidability of mathematics. The problem became a central challenge in mathematical logic.
1.2 Prior Work: Gödel, Church, and Post
Before Turing, several mathematicians had already made decisive contributions. Kurt Gödel’s incompleteness theorems (1931) showed that any sufficiently powerful axiomatic system is incomplete and cannot prove its own consistency. In 1936, Alonzo Church published a paper proving that the Entscheidungsproblem is unsolvable, using his formalism of λ-calculus and the notion of “effective calculability” as recursiveness. Independently, Emil Post developed a similar result using what he called “tag systems” and “canonical systems.” However, Church’s argument relied on a formal definition of effective calculability that was not universally accepted as capturing all possible mechanical processes. Turing’s approach provided a more intuitive, physically grounded model.
1.3 Turing’s Motivation and Approach
Alan Turing, then a fellow at King’s College, Cambridge, was influenced by Gödel’s results and by lectures of Max Newman. He sought to give a precise, operational definition of “mechanical procedure” that would be convincing to mathematicians and physicists alike. Turing’s key insight was to conceive of a human computer (a human mathematician performing calculations with paper and pencil) and then abstract that process into a simple machine. By formalizing the limitations of such a machine, he could prove that certain problems lie beyond mechanical computability. His paper was submitted in May 1936 and published later that year.
2 The Turing Machine Model
The Turing machine is a mathematical model of computation that captures the essence of any algorithmic process. It consists of an infinite tape, a read–write head, and a finite set of states. Despite its simplicity, the model is capable of simulating any computable function.
2.1 Definition of a Computing Machine
Turing defined a “computing machine” as a device that operates on a tape divided into squares, each bearing a symbol. The machine can read and write symbols, move the tape left or right, and change its internal state, all according to a finite set of instructions.
2.1.1 Tape, Head, and States
The tape is one-dimensional and unbounded in both directions. Each square initially contains a blank symbol (e.g., “0”) except for a finite sequence of input symbols. The head can read the symbol on the current square, write a new symbol, and then move one square left or right. The machine has a finite set of states, including a designated start state and one or more halting states. At any moment, the machine’s configuration is determined by the state, the tape content, and the head position.
2.1.2 Instructions and Configuration
An instruction is a quintuple of the form: (current state, scanned symbol, next symbol, movement direction, next state). For each combination of current state and scanned symbol, the machine performs the corresponding action. If no instruction applies, the machine halts. A complete configuration (instantaneous description) lists the tape content, head position, and current state. Turing showed that the evolution of configurations can itself be described in a formal, mechanical manner.
2.2 Computable Numbers
Turing defined a real number as *computable* if its infinite decimal expansion can be produced by a computing machine that prints the digits one by one, never halting, and using a finite amount of memory. Importantly, the machine must print the correct digits and eventually print any given digit in finite time.
2.2.1 Relation to Decimal Expansions
A computable number is one for which there exists a Turing machine that, when started on a blank tape, writes the digits of that number’s decimal expansion sequentially. For example, π is computable because algorithms exist to compute its digits to any desired length. Turing’s definition excluded numbers whose expansions are not effectively producible, such as those that would require an oracle to determine each digit.
2.2.2 Examples of Computable Sequences
Simple examples include all rational numbers (whose decimal expansions eventually repeat) and algebraic numbers (roots of polynomial equations). Many transcendental numbers, like π and e, are also computable. However, Turing proved that the set of computable numbers is countably infinite, whereas the real numbers are uncountable, so almost all real numbers are non-computable.
2.3 Universal Computing Machine
Perhaps the most profound contribution of Turing’s paper was the concept of a *universal computing machine*—a single machine that can simulate any other Turing machine.
2.3.1 Concept of a Universal Machine
A universal machine (U) is designed so that, when given a description of any specific Turing machine M and the input for M, it will carry out the same computation as M. In other words, U is a programmable device that can execute any program. This idea anticipated the stored-program computer central to modern computing.
2.3.2 Encoding Programs as Data
To achieve universality, Turing described how to encode the instruction table of any machine M as a sequence of symbols that can be placed on the tape of U. The universal machine then reads this “program” and simulates M’s behavior step by step. Us machine can also be described in its own notation, leading to the possibility of self-referential arguments.
3 The Entscheidungsproblem and Its Unsolvability
Turing’s main result was to show that Hilbert’s Entscheidungsproblem has no solution. He did so by linking it to the *halting problem*—the question of whether a given Turing machine will eventually halt on a given input.
3.1 Reduction to the Halting Problem
Turing argued that if the Entscheidungsproblem were solvable, then the halting problem would also be solvable. Since he could prove the halting problem unsolvable, the Entscheidungsproblem must be unsolvable as well.
3.1.1 Definition of the Halting Problem
The halting problem asks: given a description of a Turing machine M and an input w, will M eventually halt when started with w on its tape? This is a decision problem about programs. Turing showed that no Turing machine can correctly answer this question for all possible inputs.
3.1.2 Proof That No Machine Can Decide Halting
Turing’s proof uses a diagonalization argument, similar to Cantor’s diagonal proof of the uncountability of reals and Gödel’s incompleteness.
3.1.2.1 Diagonalization Argument
Assume, for contradiction, that there exists a Turing machine H that decides the halting problem: H(M, w) halts and returns “yes” if M halts on w, and “no” otherwise. Construct a new machine D that takes a description M, runs H(M, M) (i.e., asks whether M halts when given its own description), and does the opposite: if H says “yes,” D enters an infinite loop; if H says “no,” D halts. Then consider what happens when D is given its own description: if D halts, then H(D, D) says “yes,” but D would then loop; if D loops, H says “no,” but then D halts. This contradiction shows that H cannot exist.
3.1.2.2 Contradiction with Self-Reference
The core of the contradiction lies in self-application. The machine D is built to behave differently from what H predicts. Because H is assumed to be correct for all inputs, its prediction for the pair (D, D) must be both true and false—an impossibility. Thus no Turing machine can solve the halting problem.
3.2 Consequences for Hilbert’s Program
Turing next argued that if the Entscheidungsproblem were solvable, then one could build a machine that decides the halting problem. Since that is impossible, the Entscheidungsproblem is unsolvable.
3.2.1 Unsolvability of the Decision Problem
Specifically, given any first-order logic statement, one could encode the operation of a Turing machine and ask whether it will ever halt. A decision procedure for first-order logic would be able to answer that question, thereby contradicting the unsolvability of the halting problem. Hence no mechanical procedure can determine validity for all statements of first-order logic.
3.2.2 Impact on Formal Mathematics
The unsolvability of the Entscheidungsproblem demolished Hilbert’s hope that all mathematical truth could be mechanically decided. Combined with Gödel’s incompleteness theorems, it demonstrated fundamental limitations of formal systems. Mathematicians could no longer expect a universal algorithm for theorem-proving, and the nature of mathematical reasoning itself was called into question.
4 Implications and Legacy
Turing’s paper had far-reaching consequences, shaping both the foundations of mathematics and the development of practical computing.
4.1 Church–Turing Thesis
The equivalence of Turing machines, Church’s λ-calculus, and other formalisms led to the Church–Turing thesis: the claim that any function that is “effectively computable” by an algorithm can be computed by a Turing machine.
4.1.1 Equivalence of Notions of Computability
Turing himself showed that his machines can simulate Church’s λ-definable functions, and vice versa. Later, other models—such as Gödel’s general recursive functions, Post’s canonical systems, and Markov algorithms—were all proven equivalent. This convergence gave strong evidence for the thesis, which is now universally accepted in computability theory.
4.2 Development of Computer Science
The Turing machine became the foundational model for the theory of computation, directly influencing the design of real computers.
4.2.1 Stored-Program Concept
The universal Turing machine encodes the program as data on the same tape used for computation. This idea—the stored-program concept—is the basis of the von Neumann architecture used in nearly all modern computers. Turing’s paper thus provided the theoretical blueprint for general-purpose electronic computers.
4.2.2 Universal Machine as a Prototype
The universal machine demonstrated that a single device could perform any computation, given the appropriate program. This principle underlies the flexibility of microprocessors and the software industry. Turing’s work also inspired early computing projects, such as the Automatic Computing Engine (ACE) at the National Physical Laboratory.
4.3 Later Refinements
Subsequent research extended Turing’s basic model to capture a wider range of computational phenomena.
4.3.1 Variations: Multi-Tape, Non-Deterministic Turing Machines
Later theorists introduced multi-tape machines (with several tapes and heads), non-deterministic Turing machines (which can choose among multiple instructions at each step), and other variants. These models are all equivalent in power to Turing’s original deterministic single-tape machine, but they are useful for analyzing complexity classes like P and NP.
4.3.2 Oracle Machines and Relative Computability
In 1939, Turing introduced *oracle machines*—Turing machines augmented with an external “oracle” that can answer certain questions, such as the halting problem for ordinary machines. This concept, later formalized by Emil Post and others, led to the study of degrees of unsolvability and relative computability, an active area of recursion theory.