Amateurs Collaborate on Discord to Solve a Famous Computer Science Problem

A team of amateurs 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" https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/

PAPERS
- Busy Beaver Challenge website https://bbchallenge.org/
- "The Busy Beaver Frontier", S. Aaronson 2020 https://dl.acm.org/doi/10.1145/3427361.3427369
- "On Non-Computable Functions" T. Rado 1962 https://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 https://www.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: https://www.quantamagazine.org
- LIKE us on Facebook: / quantanews
- FOLLOW us Twitter: / quantamagazine

Quanta Magazine is an editorially independent publication supported by the Simons Foundation: https://www.simonsfoundation.org