I first read about the Busy Beaver function in the essay Who Can Name the Bigger Number? which is a funny story published 19 years ago, involving a “quickly name a big number” competition, where small kids will use digits, high schoolers will use exponentials, undergrads will use factorials or repeated factorials … until you get to theoretical computer scientists and/or philosophers. They will invent abstract structures to explain huge numbers. One of them is connected to Alan Turing — a person whose birthday was today (or yesterday, depending on timezone, arghh). I highly recommend reading the story. It mentions Turing Machines, DNA, intelligence as grasping big numbers, people’s phobia of big numbers; and the Busy Beaver function itself.
Then, 8 years ago, Professor Brailsford of Computerphile fame, explained the Busy Beaver game in video format (you can watch the video, and it involves the Busy Beaver game for some n: an abstract computer i.e. a Turing Machine is some abstract machine that can be in n different states, and the goal is to find a machine that works hard changing its memory without ending in an endless loop):
Throughout his video, he relates the beaver game to the function BB(n) also known as S(n): the function that counts the maximum steps for a game with n states and he goes through the first few “scores” or steps. At 13:31 he mentions that he doesn’t even wanna calculate how many Turing machines there are for n=5, much less calculate the value of the max steps.
Well, in 2022, Aaronson conjectured that BB(5) = 47,176,870 in a paper that analyzes the low-hanging fruits (as well as more difficult problems and challenges) regarding this fascinating function.
Then, some people (initiative by Tristan Stérin, [edit] but he messaged me to mention all the 20+ highly collaborative people that are producing the results!) started bbchallenge.org to solve it. You can read the story here — they read Aaronson’s paper and decided they will write independent deciders, i.e. programs that will decide the behavior of families of machines that are well-known.
This month we’ve got some proofs that are ready to be analyzed that in fact prove this.
As Tristan Stérin says:
Nonetheless, bbchallenge’s endgame approaches and we’re very excited for what comes next!
Beaverly yours,
If you want to help solve BB(5) (by taking a look at the proof or otherwise) or even take a look at BB(6), you can also join the Discord server.