Concept
The mathematical study of what fixed procedures can compute. In 1936 Church and Turing clarified its power and limits with different formal models.
Understand it in one breath
"Which functions can any algorithm compute?" In 1936 Turing idealized paper-and-pencil calculation and proved a limit on the decision problem. In modern halting-problem language, no general algorithm decides whether every arbitrary program halts. Calculating machines already existed; the paper clarified an abstract model of universal computation.
At a glance
Problem | Decidable? | Note |
|---|---|---|
Primality testing | ✓ | Sieve of Eratosthenes |
Sorting and searching | ✓ | Algorithms differ only in efficiency |
Polynomial with integer solutions (Hilbert’s Tenth Problem) | ✗ | Hilbert’s Tenth Problem — Matiyasevich, 1970 |
Halting problem | ✗ | Turing, 1936 — diagonal argument |
Do two programs compute the same function? | ✗ | Rice’s theorem (every nontrivial semantic property) |
Word problem (group theory) | ✗ | Novikov 1955 |
Undecidable problems are not exceptions but the overwhelming majority. Decidable problems are rare gems.
Key formula
Key moments
Hilbert — the Entscheidungsproblem
Is there a mechanical procedure that can decide whether every mathematical statement is true or false? It was one of Hilbert’s last great questions.
Church and Turing — independently, no
In the same period, Alonzo Church through lambda calculus and Alan Turing through his machine model independently showed that no such universal decision algorithm exists.
Turing defines the Turing machine
Turing introduced an abstract machine that captured what it means for a process to be computable — a theoretical starting point for computer science.
P versus NP — a new open problem
Work by Stephen Cook and Richard Karp crystallized the question of whether problems whose solutions can be checked efficiently can also be solved efficiently. It became a million-dollar Millennium Prize Problem.
Modern applications
The limits of compiler analysis, automated theorem proving, theoretical limits of AI, and the expressive power of programming languages.
Beyond MathVoyage
Loading…