OpenTube

The Internet Just Solved a 40-Year-Old Computer Science Mystery

Quanta Magazine

1,013,832 views

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" https://www.quantamagazine.org/amateu...

PAPERS
Busy Beaver Challenge website https://bbchallenge.org/
"The Busy Beaver Frontier", S. Aaronson 2020 https://dl.acm.org/doi/10.1145/342736...
"On Non-Computable Functions" T. Rado 1962 https://onlinelibrary.wiley.com/doi/a...
"The determination of the value of Rado’s noncomputable function
for four-state Turing machines" A. Brady, 1983 https://www.ams.org/journals/mcom/198...

--------
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

20 Comments

@doctorscoot 1 year ago

I think you ought to mention here that a general solution to the halting problem is already known to be undecidable.

@rhodri22 1 year ago

BB 6 looks hard, I'd just skip to 7

@jason3898 1 year ago

Coq is not pronounced "coke", they just didn't want to pronounce it properly.

@ellenripley4640 11 months ago

Why is this labeled as a team of amateurs, when it is lead by someone who has a PhD in computer science. I assume the rest of the group contains computer scientists too.

@VascoCC95 1 year ago

This is like a measurement of computational level achieved by the humanity, the level of the last BB found so far

@Ultimaximus 1 year ago

9:55 "A mysterious new contributor known only by a psuedonym joined in" Yeah that's how discord works, most people have usernames

@Frommerman 1 year ago

Ah yes, the Collatz Conjecture. The ultimate Nerd Sniper.

@joaofernandes9458 1 year ago

bro just call the minecraft math guys They can solve until BB(6)

@Jason9637 1 year ago

What's insane is that the current contender for BB(6) is 10↑↑15. That's 10^10^10^... 15 times! I have some big doubts about if it's even provable

@FreejackVesa 7 months ago

Tibor Radó was a fascinating man. He was placed in a Siberian prison during the Russian Revolution, escaped and went north to the arctic circle where he befriended Eskimo who helped him. Very interesting life.

@karthikkumar5822 1 year ago

I respect how people are providing, contributing to the solutions anonymously. It shifts the attention to solving the problem, eventually benefiting everyone. With names, attention kinda splits to who gets credit, overhyping media interviews, encroaching privacy, etc. As for problem solvers, he gets his interest peaked, challenges, completes and gets his/her satisfaction(dopamine).

@hinkhall5291 8 months ago

My sister took on the busy beaver challenge. She devours lots of hard wood.

@chanyy6838 1 year ago

BB(1919): Allow me to introduce myself

@yrodro 8 months ago

This problem is of special interest to Poe Dameron.

@brll5733 1 year ago

Chances that the mystery collaborator used AI to do it so fast?

@fantastic-b2m 1 year ago

it feels like they are breaking the field, like this is SO FREAKING CLOSE to the 3n+1 problem, it's just so unimaginable

@Chad.Commenter 1 year ago

I always knew that formal academic mathematicians were useless.

@magicmulder 1 year ago

8:00 I knew the name Heiner Marxen rang a bell - I know him from my computer chess days. Great guy who loves solving chess problems with software.

@Mempler 1 year ago

This reminds me a lot of how AI learns with reinforced learning tbh

@snoozbuster 1 year ago

I love these projects that involve community effort, especially when they include a community countdown like this. They're so much fun to be a part of.