Source Summary: Turing 1936
Full title: On Computable Numbers, with an Application to the Entscheidungsproblem
Authors: A. M. Turing
Affiliation: King’s College, Cambridge
Venue: Proceedings of the London Mathematical Society, Series 2, Vol. 42 (1936–37), pp. 230–265
Received: 28 May 1936; Read 12 November 1936
PDF: papers/turing-1936-on-computable-numbers-with-an.pdf
Contributions
- The Turing Machine — a formal abstract machine (tape + read/write head + states) that defines what it means to compute.
- Universal Turing Machine (UTM) — a single machine that can simulate any other Turing machine when given a description of it on the tape; proof of concept for a stored-program computer.
- Entscheidungsproblem solved (negatively) — Hilbert’s decision problem (“is there an algorithm that decides the truth of any mathematical statement?”) has no solution.
- Halting problem — no Turing machine can decide in general whether an arbitrary Turing machine will halt; first undecidability proof in a computational framework.
- Church-Turing equivalence — shown (in appendix) to be equivalent to Church’s lambda calculus notion of effective calculability.
Methodology
The Turing Machine (§1–2)
A machine with:
- An infinite tape divided into squares, each bearing a symbol or blank
- A read/write head that scans one square at a time
- A finite set of m-configurations (internal states)
- A transition table: given current state + scanned symbol → write symbol, move left/right, enter new state
The machine is fully deterministic (automatic machine, a-machine): each configuration determines the next action completely.
Computable numbers (§2)
A real number is computable if a Turing machine, started on a blank tape, will print its decimal expansion (alternating with working symbols) without ever halting. A sequence is computable if a circle-free machine prints it (never gets stuck).
Key examples shown computable: π, e, algebraic numbers, zeros of Bessel functions.
Enumeration of machines (§3–5)
Every Turing machine can be encoded as a description number (a finite integer). This allows Turing machines to be enumerated. The set of computable sequences is therefore enumerable — countably infinite — even though it includes all “naturally” computable real numbers.
The Universal Turing Machine (§6)
Turing constructs a machine U that:
- Takes as input the description number of any Turing machine M and an input
- Simulates M on that input
- Produces exactly the output M would have produced
This is the first formal proof that a single, fixed machine can compute everything any other machine can compute — the theoretical basis for general-purpose computers.
The Halting Problem (§8)
By diagonalization:
- Suppose a machine H exists that, given any machine description M and input, outputs 1 if M halts and 0 if it doesn’t
- Construct a machine K that uses H’s output to do the opposite: if H says M halts, K loops; if H says M doesn’t halt, K halts
- Apply K to its own description: contradiction → H cannot exist
Conclusion: No Turing machine can decide the halting problem. The class of undecidable problems is non-empty.
The Entscheidungsproblem (§11)
Hilbert’s 1928 decision problem asked for an algorithm that decides whether any given mathematical statement is provable. Turing shows:
- If the Entscheidungsproblem were solvable, the halting problem would be too
- The halting problem is unsolvable
- Therefore the Entscheidungsproblem has no solution
(Alonzo Church proved the same result independently via lambda calculus a few months earlier.)
Key Design Choices
Why define computing from scratch?
Rather than use existing mathematical formalisms (recursive functions, lambda calculus), Turing anchored his definition in the physical act of a human computer working on paper: finite memory states, one symbol at a time, one step at a time. This made the definition maximally concrete and convincing — if anything is computable, a Turing machine can compute it.
The m-configurations
The word “m-configuration” comes from “machine configuration” — the internal state of the machine. Turing uses the term to avoid confusion with the physical configuration of the tape. The transition table maps (m-configuration, scanned symbol) → (operation, new m-configuration).
Limitations
- The paper defines what is computable but says nothing about how efficiently — complexity theory (P vs NP, etc.) came much later
- Turing machines are an abstraction; real hardware is different (bounded memory, finite time)
- The Church-Turing thesis (that anything intuitively computable is Turing-computable) remains a thesis — it cannot be formally proven
Key References
- Gödel 1931 — Incompleteness theorems (Turing results are closely related)
- Church 1936 — Lambda calculus and effective calculability (independent, equivalent result)
- Hilbert & Ackermann 1928 — Entscheidungsproblem statement