Busy Beaver
The busy beaver function Σ(n) is the maximum number of 1s an n-state, 2-symbol Turing machine can write before halting. Watch the known champions run.
What is a busy beaver, and why is Σ uncomputable?
A busy beaver of order n is the n-state, 2-symbol Turing
machine that runs the longest before halting on a blank tape. The
function Σ(n) records the maximum number of 1s such a
machine can leave behind.
Σ grows faster than any computable function — if you could compute it,
you could solve the halting problem. So while we know
Σ(2) = 4, Σ(3) = 6, Σ(4) = 13,
and (since 2024) Σ(5) = 4098, every step beyond is a
frontier where finitely many machines hide an infinity of
questions.
Reference: Scott Aaronson, “The Busy Beaver Frontier” (2020).
| state | read 0 → write,move,next | read 1 → write,move,next |
|---|
Σ(2)=4, Σ(3)=6, Σ(4)=13 are the canonical champions. H denotes the halt state. Coloring on the tape fades older writes toward neutral.