On Computable Numbers, with an Application to the Entscheidungsproblem
Authors: A. M. Turing
Year: 1936 | Proceedings of the London Mathematical Society
Source: turing-1936-on-computable-numbers-with-an
What it is
This 1936 paper invented the concept of a Turing machine — the abstract model of computation that defines what it means to compute anything at all. In the same paper, Turing used his own machine to prove that certain problems are undecidable: no algorithm can ever solve them. The paper answered Hilbert’s Entscheidungsproblem (“is there an algorithm for mathematics?”) with a definitive no, and in doing so created theoretical computer science.
The Turing machine
Turing’s idea was to model what a human mathematician actually does when computing:
- The mathematician works on paper (the tape: an infinite sequence of squares)
- They look at one symbol at a time (the read head)
- Their behavior depends only on the symbol they see and their current mental state (m-configuration)
- They can write, erase, and move one square left or right
Formalized:
Tape: ... [ ] [1] [0] [1] [ ] ...
↑
Read head
State: q₃
Transition: (q₃, 1) → write 0, move Right, go to q₇
The machine is completely deterministic: given the current state and the scanned symbol, the transition table determines everything. No randomness, no ambiguity.
Computable numbers
A real number is computable if some Turing machine, given a blank tape, will print its digits one by one and never get stuck. Turing shows that this class includes:
- All integers and rationals
- All algebraic numbers (roots of polynomials)
- π, e, and other classical constants
But computable numbers are enumerable (countably infinite), while real numbers are uncountably infinite. So most real numbers — in a precise mathematical sense — are not computable. We cannot even write down their digits by any finite procedure.
The Universal Turing Machine
Turing’s most important construction: a single machine U that can simulate any other Turing machine.
How: encode any Turing machine M as a finite string of symbols (its “description number”), write that string on the tape of U along with an input, and U will produce exactly the output M would have produced.
This is the theoretical basis of the general-purpose computer — the same hardware runs any program, depending on what’s in memory. Before Turing, the idea of a machine that is itself programmable had no formal foundation.
The halting problem
Can we build a machine that, given any Turing machine M and an input, tells us whether M will eventually halt?
Turing proved: no.
The proof is a diagonal argument. Suppose such a machine H existed. Build a machine K that:
- Uses H to check whether K itself (applied to its own description) would halt
- If H says “yes, K halts” → K loops forever
- If H says “no, K doesn’t halt” → K halts immediately
Applying K to its own description produces a contradiction in both cases. Therefore H cannot exist.
This was the first proof that some precisely-stated mathematical problem is computationally unsolvable — not just hard, but provably impossible for any algorithm ever.
The Entscheidungsproblem
Hilbert’s 1928 decision problem asked: is there a general algorithm that, given any mathematical statement, decides whether it is provable?
Turing showed:
- If the Entscheidungsproblem were solvable, the halting problem would be solvable (by reduction)
- The halting problem is not solvable
- Therefore the Entscheidungsproblem has no solution
Mathematics cannot be fully automated. There are questions that no algorithm can answer.
(Church had proven the same result via lambda calculus slightly earlier in 1936; Turing’s proof, via his more mechanistic model, was independently arrived at and widely considered more intuitive.)
Why this matters for AI
The Turing machine defines the ceiling of what computation can do. Any AI system — neural network, language model, symbolic reasoner — runs on hardware that is a physical realization of a Turing machine. This means:
- AI systems are limited by what Turing machines can compute
- Some problems (the halting problem, certain logical questions) are forever beyond any AI
- The Church-Turing thesis — that anything “effectively calculable” is Turing-computable — frames what intelligence via computation could even in principle achieve
McCulloch & Pitts (1943) cited Turing’s work explicitly: their neural nets with feedback are Turing-equivalent.
The machine table: Turing’s notation
Turing described machines with explicit state tables, e.g., a machine to print 0101…:
| State | Symbol | Write | Move | Next State |
|---|---|---|---|---|
| b | None | 0 | R | c |
| c | None | — | R | e |
| e | None | 1 | R | f |
| f | None | — | R | b |
These tables are the direct ancestors of finite automata, regular expressions, and the transition functions in modern CS theory.
See also
- turing-1950-computing-machinery-and-intelligence — Turing’s later question: can machines think?
- shannon-1938-symbolic-analysis-of-relay-and — Circuits that implement Turing-computable functions
- mcculloch-1943-a-logical-calculus-of-the — Neural nets as Turing-equivalent computers
- boole-1854-an-investigation-of-the-laws — The Boolean algebra underlying digital logic