The Halting Problem

A question no program can answer

An interactive lesson with 8 steps, about 7 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• The halting problem asks whether a program will ever stop.
• Turing proved (1936) that no program can solve it for all programs.
• Many questions about program behaviour are undecidable in general.

Steps

1. Will it ever stop?
2. Will these halt?
3. Turing’s proof
4. The diagonal trap
5. What it means
6. Gödel’s shadow
7. Will it reach 1?
8. A halting oracle for mathematics