On Computable NumbersEdit
On Computable Numbers, with an Application to the Entscheidungsproblem, a 1936 paper by Alan Turing, marked a turning point in the foundations of mathematics and the emergence of computer science. In it, Turing introduced the notion of numbers whose decimal expansions can be produced by a finite procedure, and he formalized a simple abstract device—the machine—which can carry out such procedures. The work also connected this notion to a central question of the day: whether every mathematical problem that can be framed in a precise, rule-based way can be decided by a mechanical process. The conclusions drawn in this work helped redefine what could be achieved by formal reasoning and what lay beyond the reach of algorithmic calculation.
The paper sits at the intersection of logic, computation, and the philosophy of mathematics. It follows in the wake of efforts to prove or disprove Hilbert’s program, which sought a complete and consistent formal foundation for all of mathematics. By giving a precise model of computation and by proving limits to what such models can decide, Turing provided a concrete response to questions about decidability that had unsettled mathematicians for years. The results culminated in part in the recognition that not all mathematical questions admit a uniform procedure to determine truth, a realization that has shaped both theoretical investigations and the design of actual computing devices.
Background
The central issue addressed in the paper is the Entscheidungsproblem, or decision problem, originally posed by David Hilbert and extensions thereof. The question asked whether there exists an algorithm that can determine the truth or falsehood of any given statement of first-order logic. Turing’s investigation approached this problem by asking what would count as an effective method for performing arbitrary calculations or logical checks. He sought to formalize the intuitive notion of an algorithm or effective procedure, and to tie that notion to a concrete mechanical process.
In establishing his framework, Turing introduced a model of computation that would later be recognized as equivalent in power to other formal notions of computation. The core idea is to imagine an abstract device operating on a finite set of symbols on a tape, able to read, write, and move the tape head according to a fixed set of rules. A sequence of such operations, if finite and well-defined, constitutes an algorithm. He then defined what it means for a real number to be computable: a real number is computable if there exists such a finite procedure that, given successive inputs, outputs the digits of the number in order. Not all real numbers are computable; indeed, most real numbers are noncomputable in the sense that no finite procedure can generate their digits.
The Turing machine model
The formal device at the heart of the paper is now known as the Turing machine. A Turing machine consists of a tape that is conceptually infinite in one direction, a read/write head that can move along the tape, a finite set of internal states, and a transition rule that determines the machine’s action based on the current state and the symbol being read. At each step, the machine may write a symbol, move the head left or right, and change its state. Despite its simplicity, the model captures the essential features of algorithmic computation.
A key insight is the universality of a single machine that can simulate any other Turing machine. Given a description of another machine and its input, a universal machine can replicate the latter’s behavior. This universality laid the groundwork for the modern concept of programmable digital computers, where general-purpose hardware can run a wide variety of software by interpreting instructions encoded as data.
In his discussion, Turing also introduced the notion of computable numbers as those that can be produced by such machines. The emphasis on an explicit, mechanical process to generate digits of a real number provided a rigorous anchor for the informal notion of effective calculability. The distinction between computable and noncomputable numbers has since become a standard theme in the theory of computation and in the philosophy of mathematics.
Undecidability and the Entscheidungsproblem
A central result of the work is the demonstration that there is no general algorithmic method to decide, for every possible formal statement, whether that statement is true in all interpretations of a given formal system. In other words, the paper shows that the Entscheidungsproblem is unsolvable in general when treated within the standard framework of mechanical computation. Turing’s argument relies on a diagonalization construction that yields a contradiction if one assumes the existence of a universal decision procedure for all machines or all logical statements.
This line of reasoning leads to the introduction of the halting problem: the problem of determining, given a description of a Turing machine and an input, whether the machine will eventually halt. The halting problem is undecidable: no single algorithm can determine the answer for all possible machine-input pairs. The undecidability of the halting problem implies, in turn, the undecidability of the broader decision problem for first-order logic, under the assumptions laid out by Turing’s model of computation.
The implications of these results extended beyond pure logic. They established intrinsic limits to what can be achieved by mechanical procedures, thereby reshaping expectations about the reach of formal methods in mathematics. The work also contributed to a broader program of understanding computation as a fundamental aspect of both mathematics and the design of machines, influencing later work in automata theory, computer architecture, and the theory of programming languages.
Legacy and connections
Turing’s framework provided a precise and durable foundation for the field of computability theory. The paper helped catalyze the development of several complementary strands of thought. The concept that the power of computation could be captured by a simple, yet universal, abstract machine led to the modern idea of programmable computers and to the quest for a formal description of what can be computed in principle. The results fostered parallel developments, including the formulation of the Church–Turing thesis, which posits that any function that is effectively computable by an algorithm can be computed by a Turing machine or by any of the other equivalent formal models such as the lambda calculus.
The notion of universality, illustrated by the universal machine, presaged the architecture of contemporary computers, where a single hardware substrate runs a variety of software programs. The ideas also influenced the study of automata, formal languages, and complexity theory, shaping how researchers think about the limits of algorithms and the resources needed to perform computation.