What is the most productive simple program? A game against computability itself.
Play It
Characterization
The Busy Beaver problem asks: among all Turing machines with n states and a two-symbol alphabet that eventually halt, which one runs the longest before stopping? Equivalently, which produces the most output? The function BB(n), which maps the number of states to the maximum number of steps, was defined by Tibor Radó in 1962. It grows faster than any computable function — faster than exponential, faster than factorial, faster than any function a computer program could calculate. This is not a statement about the difficulty of computing BB(n); it is a proof that BB(n) is uncomputable. No algorithm can calculate it for all n. Yet individual values can be determined by exhaustive analysis. BB(1) = 1. BB(2) = 6. BB(3) = 21. BB(4) = 107. In July 2024, the bbchallenge.org collaborative project — a distributed effort by dozens of researchers and enthusiasts — formally proved that BB(5) = 47,176,870, closing a problem that had been open for over sixty years. BB(6) and beyond remain unknown; the candidates involve Turing machines whose behaviour encodes unsolved problems in mathematics, meaning that determining BB(6) may require resolving open conjectures. The Academy hosts the Busy Beaver in the Mind School because it is a competition — a game among tiny programs — whose stakes are the boundary between the knowable and the unknowable.
Lineage
Tibor Radó, "On Non-Computable Functions," Bell System Technical Journal 41(3), 1962. The early values BB(1) through BB(4) were determined over decades by Lin and Rado (1965), Brady (1983), and Marxen and Buntrock (1990). The BB(5) = 47,176,870 result was established by the bbchallenge.org collaboration in July 2024, using a combination of exhaustive enumeration and formal verification in Coq. Scott Aaronson, "The Busy Beaver Frontier," SIGACT News, 2020, provides a comprehensive survey of the connections between BB(n) and open problems in mathematics. Pascal Michel maintains the definitive historical table at bbchallenge.org.
Quests
The Magus
Construct and enumerate all halting Turing machines for a small number of states (n = 2 or n = 3) on a two-symbol alphabet. For each halting machine, count the number of 1s written on the tape. Verify the known Busy Beaver values — BB(2) = 4, BB(3) = 6 — by exhaustive search or reasoned elimination. Reflect on how the enumeration grows and why exhaustive methods fail for n ≥ 5.
The Adventurer
Select one of the known Busy Beaver champion machines — the BB(4) champion (13 ones in 107 steps) or the BB(5) champion (47,176,870 ones) — and step through its execution by hand or with a simulator for at least 50 steps. Record the tape contents at key moments. Attend to the pattern: does the machine's behaviour look purposeful, random, or something in between? Note the moment when you first sensed what the machine was "trying to do."
Explain the Busy Beaver problem to someone who has heard of Turing machines but not of uncomputability. Define BB(n); give the known values for n = 1 through 5; explain why BB is uncomputable (connect it to the halting problem). Cite Radó's 1962 paper, the 2024 bb5.org collaborative determination of BB(5), and Aaronson's work connecting BB(748) to the Goldbach conjecture. Conclude with a note on what it means for a well-defined function to have values that no algorithm can ever compute.