Busy Beaver Functions

The Busy Beaver Game is the search for Turing machines which maximize various Busy Beaver Functions. All Busy Beaver functions are non-computable. There are several, related functions with different authors referring to to one or the other as "the Busy Beaver function". Therefore, it is recommended that you use a more specific designation when referring to one specific Busy Beaver function.

The two most commonly used Busy Beaver functions are:

• The Maximum Shift function $S(n,m)$ which is the most commonly used Busy Beaver function by bbchallenge and is often called $BB(n,m)$ here.
• The Maximum Score function $\mathrm{\Sigma }(n,m)$ which is Tibor Radó's original Busy Beaver function.

James Harland wrote an article "The Busy Beaver, the Placid Platypus and other Crazy Creatures" in 2006 giving various fanciful names to these various functions.

Max Shift Function S(n, m)

The Maximum Shift or Maximum Step function is the largest number of steps (or shifts) that any Turing machine (of a certain size) takes before halting. It was introduced by Tibor Radó in his seminal Busy Beaver paper. He used the notation $S(n)$ to define it for Turing machines with $n$ states and 2 symbols. This was later extended to $S(n,m)$ for $n$ states and $m$ symbols.

Harland calls this the "frantic frog" function $ff(n)$.

In his 2020 Survey, Scott Aaronson introduced the notation $BB(n,m)$ for the Max Shift function and refers to it as "the" Busy Beaver function.

Max Score Function Σ(n, m)

The Maximum Score function is the largest number of non-zero symbols left on the tape by any halting Turing machine (of a certain size) at the moment it halts. It was also introduced by Tibor Radó in his seminal paper. He called it the "score" of the Turing machine. He used the notation $\mathrm{\Sigma }(n)$ to define it for Turing machines with $n$ states and 2 symbols. This was later extended to $\mathrm{\Sigma }(n,m)$ for $n$ states and $m$ symbols.

Harland calls this the "busy beaver" function $bb(n)$. Before Aaronson's survey, this was the function that most people called "the" Busy Beaver function.

Ambiguity of the notation BB(n,m)

As stated above, the use of notation BB(n) or BB(n,m) has historically ambiguously referred to either Radó's S or \Sigma function. bbchallenge.org uses the convention BB = S.