Computability asks what can be computed at all, whatever the time or memory. Its answer is a precise boundary: some well-defined problems have no algorithm, ever. The halting problem is the famous one. Knowing the boundary tells you why perfect bug finders, virus detectors and program verifiers cannot exist.
Key concepts
- Models of computation: Turing machines, the lambda calculus and recursive functions define the same set of computable functions.
- Church-Turing thesis: the claim that these models capture everything an algorithm can do.
- Undecidability: the halting problem has no algorithm; the proof uses diagonalisation.
- Reductions: showing a new problem undecidable by turning the halting problem into it.
- Rice's theorem: every non-trivial question about what a program does is undecidable.
Vocabulary
- Decidable: some algorithm always halts with a correct yes or no.
- Semi-decidable: an algorithm halts on yes answers but may run forever on no answers.
- Universal machine: a machine that runs any other machine from its description, the ancestor of the stored-program computer.
- Diagonalisation: building an object that differs from the i-th item of a list in its i-th place.
What to study, in order
- Simulate a Turing machine in a few dozen lines and write a machine that adds two numbers.
- Read the diagonal argument for the uncountability of the reals, then the same idea for halting.
- Prove the halting problem undecidable and reproduce the proof in your own words.
- Use reductions to show other problems undecidable, such as program equivalence.
- Meet the lambda calculus and see why it computes the same functions.