The problem
BB(n) denotes the maximum number of steps made by any halting n-state, 2-symbol Turing machine started on a blank tape. Determine BB(5) — equivalently, settle the behaviour of every 5-state machine (halting ones and the "holdouts").
The Fifth Busy Beaver Number BB(5)
historicReferences
- primaryhttps://bbchallenge.org/
History & significance
Radó introduced busy beavers in 1962; Lin & Radó settled BB(3) in 1965; Allen Brady pinned BB(4) in 1983. BB(5) resisted because its holdouts brushed against Collatz-like iterated maps. Beyond BB(5) lies undecidability proper: BB(6) is independent of ZFC-set-theory territory via Rayo-style encoding, and BB(74824) literally encodes consistency statements.
Connected problems
The resolution (computer-assisted proof)
Settled 2 July 2024 by the bbchallenge collaboration (30+ contributors, led by Tristan Stérin, Cosmo Wolf et al.): every one of the ~181 million candidate machines classified, holdouts dispatched by hand-crafted proofs about their behaviour (including machines simulating Collatz dynamics), and the entire classification formally verified in the Coq proof assistant. BB(5) = 47,176,870. The first open value of the Busy Beaver function to fall — and, fittingly, the last one that ever will fall to anything short of new mathematics.