Busy Beavers

The fastest-growing function

An interactive lesson with 6 steps, about 5 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 n-state busy beaver is the longest-running halting n-state machine.
• Step records: 1, 6, 21, 107, 47,176,870 (proved 2024).
• The busy-beaver function is uncomputable: it grows faster than any computable function.

Steps

1. A competition
2. How long?
3. Three states
4. How many contestants?
5. Unimaginably big
6. Why can’t we compute it?