**Summary**
The video explains the *Busy Beaver* problem, introduced by mathematician Tibor Rado. A Busy Beaver \(BB_n\) is the Turing machine with \(n\) rules that runs the longest before halting; the number of steps it takes is the Busy Beaver number. Rado showed that determining \(BB_n\) is uncomputable—there is no general algorithm to find it, so each candidate must be examined individually.
Because any mathematical statement can be encoded as a Turing‑machine program, knowing a specific Busy Beaver number would settle famous open problems. For example, if we knew \(BB_{27}\) we could decide the Goldbach conjecture: a program that searches for a counter‑example halts iff it finds one, and it must halt within \(BB_{27}\) steps if it halts at all. Similar reductions exist for the Riemann hypothesis and other unsolved questions.
The video traces the historical effort to compute Busy Beaver numbers:
- \(BB_1 = 1\) and \(BB_2 = 6\) are trivial.
- In the mid‑1960s, Allen Brady and others found \(BB_3 = 21\).
- Brady later proved \(BB_4 = 107\) after years of work.
- For \(BB_5\) the search space exploded to ~17 trillion 5‑rule machines. A 2021 online collaboration—the *Busy Beaver Challenge*—led by hobbyist mathematicians (many without formal training) built a database of ~88 million candidates, eliminated non‑halting machines, and eventually proved that a particular 5‑rule machine halts after **47,176,870 steps**. This was verified with a 40,000‑line proof in the Coq proof‑checking system, confirming \(BB_5 = 47{,}176{,}870\).
The effort revealed the extreme difficulty of the problem: \(BB_6\) is already known to be astronomically larger (a tower of exponentials far beyond the age of the universe), suggesting we may never know \(BB_6\) or higher Busy Beaver numbers.
The story highlights how a loose‑knit, passion‑driven community, using modern tools like proof assistants, can solve a problem that resisted experts for decades, illustrating the human drive to explore the unknown. The video ends with a plug for the educational series *Becoming Human* on Nebula.
1. Tibor Rado defined the Busy Beaver problem: for each n, find the n‑rule Turing machine that runs the longest before halting.
2. The Busy Beaver number BBₙ is the maximum number of steps taken by any halting Turing machine with n rules.
3. BB₁ = 1 step.
4. BB₂ = 6 steps.
5. Determining BBₙ for arbitrary n is uncomputable; no general algorithm can compute it.
6. The halting problem proves there is no reliable method to decide whether an arbitrary Turing machine will halt.
7. A program that tests the Goldbach conjecture can be written as a 27‑rule Turing machine; knowing BB₂₇ would decide the conjecture.
8. Similar constructions exist for other unsolved problems such as the Riemann hypothesis.
9. There are over 5 million distinct 3‑rule Turing machines and over 7 billion distinct 4‑rule Turing machines.
10. Allen Brady discovered the third Busy Beaver, which halts after 21 steps.
11. Brady later identified a 4‑rule machine that halts after 107 steps, which was proven to be the fourth Busy Beaver.
12. The Busy Beaver Challenge, an online collaboration, proved that a 5‑rule machine halting after 47,176,870 steps is the fifth Busy Beaver (BB₅).
13. The machine nicknamed “Skelet #1” was shown to be non‑halting only after more than a trillion‑trillion steps.
14. The correctness of the BB₅ proof was verified using the Coq proof‑checking language by participant mei.
15. BB₆ is known to be at least a power tower of tens of height 11 (10↑↑11) steps.
16. There are nearly 60 quadrillion distinct 6‑rule Turing machines.
17. Allen Brady, who found BB₃ and BB₄, died a few weeks before the BB₅ proof was completed at age 90.
18. The Busy Beaver problem illustrates the limits of what can be computed and connects to fundamental questions in mathematics.