“On Computable Numbers, with an Application to the Entscheidungsproblem” is a seminal 1936 paper by Alan Turing that established the theoretical foundations of computer science. The paper introduced the concept of the Turing machine—an abstract model of computation that remains central to theoretical computer science today.
The Problem
The paper addressed the Entscheidungsproblem (German for “decision problem”), posed by mathematician David Hilbert in 1928. Hilbert asked whether there exists a general algorithm that could determine the truth or falsity of any mathematical statement.
Turing’s answer was no—and in proving this, he invented modern computer science.
The Turing Machine
To rigorously define what an “algorithm” means, Turing conceived of an abstract computing device now called a Turing machine[1]:
- An infinitely long tape divided into cells, each containing a symbol
- A head that can read and write symbols on the tape
- A state register that stores the machine’s current state
- A finite table of instructions that determine behavior based on current state and symbol
Despite its simplicity, Turing proved that this machine could compute anything that is computable—a result known as the Church-Turing thesis.
Key Results
The paper established several foundational results[2]:
- Universal computation: A single Turing machine can simulate any other Turing machine if given the right program (the “universal Turing machine”)
- The halting problem: It is impossible to create an algorithm that determines whether any given program will eventually halt or run forever
- Uncomputability: Some well-defined mathematical problems have no algorithmic solution
Impact
“On Computable Numbers” is one of the most influential papers in the history of mathematics and computer science:
- It provided the theoretical basis for all programmable computers
- The universal Turing machine concept anticipated stored-program computers by a decade
- It established fundamental limits on what can be computed
- It created the field of computability theory
Every digital computer today is essentially a physical realization of Turing’s abstract machine.
Sources
- Stanford Encyclopedia of Philosophy. “Turing Machines.” Comprehensive explanation of Turing machines and their significance.
- Wikipedia. “On Computable Numbers.” Overview of the paper’s key results and historical context.