Amateurs Just Solved a 30-Year-Old Math Problem

The video explores the Busy Beaver problem—a deceptively simple question about the longest a program can run before halting—which has baffled mathematicians for over 60 years and exposes fundamental limits of computation and logic. It explains how Tibor Rado proved this question is uncomputable, meaning no general algorithm can solve it, and how knowing certain Busy Beaver numbers would resolve famous unsolved problems like Goldbach's conjecture. After decades of stagnation, an unlikely group of online math enthusiasts with no formal academic credentials achieved a major breakthrough in 2024 by determining BB(5), the fifth Busy Beaver number, which halts after 47,176,870 steps. Their success depended on a proof-checking program that made errors virtually impossible, confirming the result beyond doubt. The story highlights that curiosity and collective determination can push the boundaries of human knowledge, even as larger Busy Beaver numbers like BB(6) remain hopelessly out of reach.

• ▶ 0:01 The section opens with a deceptively simple question: what is the longest time a program can run before it stops—ranging from a year to the age of the universe.

• ▶ 0:18 The question matters because it has baffled mathematicians for over 60 years, connects to famous unsolved problems, and reveals the limits of mathematical logic and human knowledge.

• ▶ 0:38 After 30 years of no progress, a major breakthrough came last year—but the strange part is how it happened: not by university researchers, but by an unlikely group of online math enthusiasts with no formal academic education.

• ▶ 1:26 Rado asked not what computers can solve, but what problems they cannot solve—seeking the ultimate limits of computation.
• ▶ 2:04 Turing machines are simple theoretical devices that capture exactly what it means to compute, and form the blueprint for all modern computers.
• ▶ 4:47 Rado discovered the Busy Beaver problem is uncomputable: there is no general algorithm to find Busy Beaver numbers, proving a problem computers cannot solve.
• ▶ 6:42 If we knew BB27, we could solve Goldbach's conjecture: the 27-rule machine halts within BB27 steps only if a counterexample exists; running longer proves it never halts.
• ▶ 8:03 Computing Busy Beaver numbers is infeasible because the number of Turing machines grows more than exponentially (over 7 billion 4-rule machines) and each must be examined individually.
• ▶ 8:42 The halting problem blocks the way: no reliable method can tell whether a machine ever halts, making it impossible to know which machines qualify for the Busy Beaver search.
• ▶ 9:43 Allen Brady took on the Busy Beaver problem, coding a program to discard obvious non-halting machines, but had to drive 90 miles to use a computer in Beaverton.
• ▶ 10:32 Rado and grad student Shen Lin beat Brady to it, finding the third Busy Beaver: a machine that halts in 21 steps.
• ▶ 11:09 Brady later found a 4-rule machine halting in 107 steps, then spent several more years proving it was the fourth Busy Beaver.
• ▶ 11:25 In April 2024, the Busy Beaver Challenge determined BB(5) despite nearly 17 trillion 5-rule Turing machines.
• ▶ 11:49 A Dortmund competition seeking BB5 produced no definitive winner, but a 5-state machine was discovered that halted after 47,176,870 steps, becoming the leading candidate for the fifth Busy Beaver.
• ▶ 13:14 Tristan Sterin compiled a database of over 88 million potential Busy Beaver machines, then founded the online Busy Beaver Challenge community to classify them all.
• ▶ 14:36 Contributors Shawn Ligocki and Pavel Kropitz proved that the notoriously difficult Skelet #1 never halts, settling into an infinite loop only after more than a trillion trillion steps.
• ▶ 15:11 The team's biggest obstacle was proving that their thousands of lines of code were completely free of errors, since any tiny bug would invalidate the entire BB(5) result.
• ▶ 15:30 A "proof checker" emerged as the solution—a program designed to reject any logical error, making mistakes virtually impossible and confirming the proof's validity beyond doubt.
• ▶ 16:17 mxdys announced the finished Coq proof of BB(5), compiled into a massive 40,000-line proof on May 10th, 2024—the final step confirming the 47-million-step Turing machine as the fifth Busy Beaver.
• ▶ 17:00 The next milestone, BB6, is already being explored but looks out of reach: BB6 is proven to be at least a power tower of ten 10s, a runtime beyond the scale of the universe's lifetime.
• ▶ 17:36 BB5 may be the last Busy Beaver number humanity ever knows, though nearly 60 quadrillion 6-rule machines remain and the odds are strongly against solving it.
• ▶ 18:04 The story shows that when people genuinely want to solve something, they find a way, and this curiosity is central to being human.

• ▶ 0:01 Introduction: The Longest-Running Program Question (0:01 - 1:17) - Sets up the central question and introduces the Busy Beaver challenge and its unlikely solvers.
• ▶ 1:17 Turing Machines and Rado's Busy Beaver Game (1:17 - 5:44) - Explains Turing machines, halting behavior, and Rado's uncomputable Busy Beaver numbers and game.
• ▶ 5:44 From Goldbach to the Halting Problem (5:44 - 9:37) - Links Busy Beaver numbers to Goldbach's conjecture and explains why no general halting test can exist.
• ▶ 9:37 Early BBs and the Road to BB(5) (9:37 - 11:46) - Covers the discovery of the third and fourth Busy Beavers and points toward the BB(5) quest.
• ▶ 11:46 The Busy Beaver Challenge: Skelet #1 and the Hardest Machines (11:46 - 14:55) - Recounts the modern search, including the Dortmund machine, Tristan Sterin's efforts, and Skelet #1's classification.
• ▶ 14:55 Verification and Proof of BB(5) (14:55 - 17:00) - Details proof-checking, the Coq formal proof, and the completion of BB(5).
• ▶ 17:00 What's Next and Closing (17:00 - 20:04) - Looks ahead to BB(6), the odds of solving it, and closes on human curiosity and a Nebula sponsorship pitch.