Paper: On Computable Numbers, with an Application to the Entscheidungsproblem

Context and motivation
Alan Turing addresses foundational questions about the nature of computation and the limits of mechanical procedures. The work responds to contemporaneous efforts to formalize mathematics and to Hilbert's Entscheidungsproblem, which asks for an algorithm to decide the truth of any formal mathematical statement. Turing reframes computation as a precise, manipulable process that can be studied mathematically.
Rather than relying on intuitive descriptions of "effective calculability," Turing constructs a simple, rigorous model that captures the essential operations of a human "computer" following a set of rules. This move provides the clarity needed to ask which problems can be solved by such mechanical procedures and which lie beyond their reach.

Formal model: the Turing machine
Turing defines the Turing machine as an abstract device consisting of a finite control, an infinite tape divided into squares, and a head that reads and writes symbols on the tape and moves left or right. The machine's behavior is governed by a finite table of instructions that specifies, for each combination of the current state and the symbol being read, what symbol to write, which direction to move, and what the next state should be.
This simple, minimal model encapsulates the notion of algorithmic procedure: anything that can be computed by a disciplined mechanical process can be carried out by a Turing machine. The model deliberately abstracts away from human or physical implementation details while preserving the essential operations of symbol manipulation.

The Universal Turing Machine
A central innovation is the construction of a Universal Turing Machine (UTM) that can simulate any other Turing machine when provided with a description of that machine and its input encoded on the tape. The UTM demonstrates that a single fixed machine can execute arbitrary computations by interpreting the encoded instructions of other machines, thereby separating hardware from program.
This universality establishes the theoretical basis for programmable computers: programs can be represented as data and processed by a general-purpose machine. The idea that a single device can be made to perform any computable task foreshadows the architecture of modern computers and clarifies the power and limits of mechanical computation.

Undecidability and the Entscheidungsproblem
Turing uses his formalism to show that certain problems are undecidable: no Turing machine can solve them in general. He proves that there is no algorithm to determine, for every possible Turing machine and input, whether the machine will ever halt (the halting problem). By a reduction from the halting problem, he demonstrates that Hilbert's Entscheidungsproblem has no solution; no mechanical procedure can decide the truth of all mathematical statements in a sufficiently expressive formal system.
The argument hinges on encoding machines and their inputs as data that can be manipulated by other machines, and on constructing self-referential situations that lead to contradiction if a general decision procedure were to exist. These results place fundamental limits on what can be achieved by algorithmic methods.

Philosophical and practical consequences
The paper crystallizes the notion of effective computability and, together with contemporaneous work by Church, yields the Church–Turing thesis: the claim that the Turing machine model captures the informal notion of algorithmic computation. This conceptual clarity transformed logic, mathematics, and computer science by delineating what can be computed and by establishing a rigorous framework for complexity and computability theory.
Beyond foundational concerns, the ideas of universality and program-as-data laid the groundwork for stored-program computers and influenced the development of programming languages, algorithms, and theoretical computer science. The legacy endures in both deep philosophical discourse about mind and machine and in the practical architecture of modern computing.