The Busy Beaver problem asks, for Turing machines with a fixed number N of rules, what is the maximum number of steps any halting machine can take before stopping; this value is denoted BB(N). While BB(1)=1, BB(2)=6 and BB(3)=21 are trivial, BB(4)=107 was proved only in 1974, and BB(5) remained open for decades. In 2022 Tristan Stérin launched the Busy Beaver Challenge, creating a distributed effort to narrow the astronomical search space (≈17 trillion five‑rule machines) to a manageable set. Participants wrote “decider” programs that eliminated most candidates, leaving only a handful of unresolved machines that required manual, non‑computer analysis. Over two years the community reduced the contenders to a single machine, whose halting behavior had been conjectured in 1983 by Heiner Marxen and Jürgen Buntrock (47,176,870 steps) but never proven. In April 2024 an anonymous contributor using the pseudonym mxdys supplied a machine‑checked proof in the Coq proof assistant, confirming that Marxen and Buntrock’s machine is indeed the fifth Busy Beaver: **BB(5)=47,176,870**. The proof is now being translated into a human‑readable form. The success relied on massive online collaboration, shared tools, and independent verification. The team has already turned to BB(6), but with ~60 quadrillion possible six‑rule machines and a candidate whose halting status mirrors the Collatz conjecture, solving BB(6) appears currently out of reach.
1. The Busy Beaver problem asks, for a Turing machine with N rules, what is the maximum number of steps it can take before halting; this maximum is denoted BB(N).
2. The problem was formulated by Hungarian mathematician Tibor Radó in 1962.
3. Turing machines were conceived by Alan Turing in the 1930s.
4. A Turing machine consists of an infinite tape (cells holding 0 or 1), a head that reads/writes and moves left/right, and a set of instructions (program) that tells the machine what to do at each step.
5. Turing machines can compute anything that is computable by algorithms.
6. A machine’s program can have any number of rules, summarized in a table with one row per rule and two columns (for input 0 or 1).
7. Each rule specifies what symbol to write, which direction to move the tape, and the next rule to follow.
8. Programs either halt (stop) or run forever in an infinite loop; useful programs are those that halt.
9. The halting problem asks whether a given Turing machine will halt or run forever; it is undecidable.
10. For each N, the Busy Beaver is the machine that runs the longest before halting; its step count is BB(N).
11. Known values: BB(1)=1 step, BB(2)=6 steps, BB(3)=21 steps.
12. BB(4)=107 steps, proved by Allen Brady in 1974.
13. In 1983, Heiner Marxen and Jürgen Buntrock identified a 5‑rule Turing machine that halts after 47,176,870 steps and conjectured it to be BB(5).
14. There are nearly 17 trillion possible 5‑rule Turing machines.
15. In 2022, Tristan Stérin launched the Busy Beaver Challenge website to solve BB(5) collaboratively.
16. Stérin’s program reduced the search space from trillions to 88 million machines by eliminating redundancies and those that halt earlier than the Marxen‑Buntrock candidate.
17. The team used “decider” programs to determine halting behavior, each eliminating 90‑99 % of remaining unsolved machines.
18. Iterative reduction narrowed the contenders to a single holdout machine.
19. In April 2024, contributor mxdys provided a Coq computer‑assisted proof confirming that the Marxen‑Buntrock machine halts after 47,176,870 steps and is indeed BB(5).
20. For N=6, there are nearly 60 quadrillion possible Turing machines; one specific machine’s halting question resembles the Collatz conjecture, and solving BB(6) is currently considered impossible with human effort.