Departure question
Find the edge of solvabilityPort 1 of 5Where two intuitions collide
Defining computation precisely made it possible to prove that some problems cannot be decided by any general program.
This voyage is an editorial path for understanding, not a claim of direct historical influence or sole invention.
"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.
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.
The mathematical study of what fixed procedures can compute. In 1936 Church and Turing clarified its power and limits with different formal models.
Ports in time
Follow the scenes to see problems, notation, standards of proof, and applications changing across different times and places.
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.
No reliable place is given, so time continues without an invented pin
Continue through the world of this yearIn the same period, Alonzo Church through lambda calculus and Alan Turing through his machine model independently showed that no such universal decision algorithm exists.
No reliable place is given, so time continues without an invented pin
Continue through the world of this yearTuring introduced an abstract machine that captured what it means for a process to be computable — a theoretical starting point for computer science.
No reliable place is given, so time continues without an invented pin
Continue through the world of this yearWork 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.
No reliable place is given, so time continues without an invented pin
Continue through the world of this yearThe limits of compiler analysis, automated theorem proving, theoretical limits of AI, and the expressive power of programming languages.
Curated sources and problems. Bring one discovery back from OEIS, Project Euler, MathOverflow, or arXiv.
No concept belongs to one person
These are not inventor credits. They are different ports: opening a problem, sharpening a language, or carrying it into another world.
Number lenses
These numbers are editorial lenses for the voyage, not required prerequisites.
Distinguishable states such as blank and zero let finite rules carry a long computation forward.
Open the number voyage
Encoding symbol strings and proofs as natural numbers turns procedures themselves into mathematical objects.
Open the number voyage
Cross mechanical procedures, proof, quantum computation, learning, and strategy to explore the limits of calculation and choice.
Open the number voyage
Concept genealogy
Concepts arriving from before
Current port
Computability
Concepts opened from here
Only direct editorial links are shown; this is not a complete learning order or historical influence line.
