Busy Beaver: The Hardest Game in Computer Science @QuantaScienceChannel
Busy Beaver: The Hardest Game in Computer Science  @QuantaScienceChannel
Uploaded April 2025 | Updated November 2026, 1 day ago
A team of strangers recently came together in an online collaboration called the Busy Beaver Challenge to pin down the value of BB(5), the fifth "busy beaver" number — a notoriously difficult problem in theoretical computer science. The busy beaver problem, or “game,” involves finding the Turing machine with a given number of states that runs for the longest series of steps before halting. Using collaborative tools and the Coq proof assistant to verify their work, the team proved that BB(5) equals 47,176,870. The landmark result explores the limits of computation and the boundaries of what is knowable in mathematics.

Read Ben Brubaker's excellent Quanta Magazine Article for more details: "With Fifth Busy Beaver, Researchers Approach Computation’s Limits" quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702

PAPERS
- Busy Beaver Challenge website bbchallenge.org
- "The Busy Beaver Frontier", S. Aaronson 2020 dl.acm.org/doi/10.1145/3427361.3427369
- "On Non-Computable Functions" T. Rado 1962 onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1962.tb00480.x
- "The determination of the value of Rado’s noncomputable function
for four-state Turing machines" A. Brady, 1983 ams.org/journals/mcom/1983-40-162/S0025-5718-1983-0689479-6

--------
CHAPTERS
00:00 What is the Busy Beaver problem?
01:05 How does a Turing machine work?
02:35 Programs that halt versus getting stuck in endless loops: the Halting Problem
04:38 How to play the Busy Beaver game
05:26 BB(1), BB(2), BB(3), BB(4) solutions
06:38 The Busy Beaver Challenge tackles BB(5)
07:31 The history of the search for BB(5)
08:10 The Busy Beaver Challenge methodology
08:48 Coding 'deciders'' to shorten the list of contenders
09:49 Mysterious contributor confirms BB(5) solution
10:09 Coq proof of BB(5)
10:54 Is BB(6) solvable?

--------
- VISIT our website: quantamagazine.org
- LIKE us on Facebook: / quantanews
- FOLLOW us Twitter: / quantamagazine

Quanta Magazine is an editorially independent publication supported by the Simons Foundation: simonsfoundation.org
Busy Beaver: The Hardest Game in Computer ScienceWhat Is the True Promise of Quantum Computing? | PODCAST: The Joy of WhyPlate Tectonics: The Mystery of Earths Many FacesHow NASA’s Webb Telescope Will Transform Our Place in the UniverseAlessio Figalli: A Traveler Who Finds Stability in the Natural WorldBlack Hole Jets: One of the Biggest Mysteries in the UniverseThe Cosmologist Challenging EinsteinDark Energy: Probing the Biggest Mystery in PhysicsDecoding Math’s Famed Fractal: The Mandelbrot SetHow Physicists Created a Holographic Wormhole in a Quantum ComputerEdward O. Wilson on the Evolution of Social BehaviorsThe Sphere-Packing Problem in High Dimensions
Quanta Magazine |

Busy Beaver: The Hardest Game in Computer Science

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER