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 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 generally called $BB(n,m)$ here.
• The Maximum Score function $\Sigma (n,m)$ which is Tibor Radó's original Busy Beaver function.

where $n$ denotes the number of states and $m$ the number of symbols.

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, and starting with a blank tape) 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. Notably, the halting transition counts as a step, so the TM with rule A0 -> 1RZ halts in 1 step.

Ben-Amram calls this the $time(n)$ function. Harland calls it the "frantic frog" function $ff(n)$.

In his 2020 Busy Beaver Frontier survey, Scott Aaronson used the notation $BB(n,m)$ for the Max Shift function and referred to it as "the" Busy Beaver function.

Max Score Function Σ(n, m)

The Maximum Score function is the largest number of ones (or non-zero symbols in general) left on the tape by any halting Turing machine (of a certain size, and starting with a blank tape) 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 $\Sigma (n)$ to define it for Turing machines with $n$ states and 2 symbols. This was later extended to $\Sigma (n,m)$ for $n$ states and $m$ symbols.

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

Other Busy Beaver functions

In addition to the above functions, there are a couple of others that have appeared in the literature:

• Maximum space: Ben-Amram calls this $space(n)$, bbchallenge calls it BB_SPACE(n) or $BB_{space}(n)$. This is the total number of tape cells read before halting. According to Ben-Amram, it includes the starting cell, but not necessarily the cell the halting transition moves to.
• Maximum consecutive ones: Ben-Amram calls this $num(n)$. A TM only qualifies if it halts with all ones consecutive on tape.
• $N_{e}$ function: Radó formulated the number of halting machines in terms of the set of all valid busy beaver entries $M,s$ where $M$ is the Turing machine, and $s$ is the exact number of steps the halting Turing machine took. The set of all halting $n$-card machines is denoted $E_{n}$, and the cardinality of this set is denoted $N_{e}(n)$ The number of $n$-card Turing machines that halt after exactly or not more than s steps are respectively denoted $N(s,n)$ and $G(s,n)$.
• Blanking busy beaver: $BLB(n,m)$ is the largest of steps done by any Turing machine with n states and m symbols before blanking the tape.
• Beeping busy beaver: $BBB(n,m)$ is the largest of steps done by any Turing machine with n states and m symbols before quasihalting.
• Busy periodic beaver: $BBP(n,m)$ is the largest period of any cycler or translated cycler with n states and m symbols.
• Busy preperiodic beaver: $BBS(n,m)$ is the largest preperiod of any cycler or translated cycler with n states and m symbols.
• Higher order busy beaver functions:
• BB_L(n) (busy beaver for L programs):People have also studied variants with a 2-dimensional tape, or where the tape head is allowed to stay still in addition to moving left or right, etc. More broadly, given any programming language L, whose programs consist of bit-strings, one can define a Busy Beaver function for L-programs:BB_L(n) := max_{P∈L∩{0,1}}^≤n_{: s(P)<∞}s(P) where s(P) is the number of steps taken by P on a blank input. Alternatively, some people define a “Busy Beaver function for L-programs” using Kolmogorov complexity. That is, they let BB’_L(n) be the largest integer m such that K_L (m) ≤ n, where K_L(m) is the length of the shortest L-program whose output is m on a blank input.
• $R(n)$ (The runtime spectrum function): $T(n)$ is the set of $n$-state Turing machines, and $s(M)$ is the running time of machine $M$ on an all-0 input tape. Let $R(n)$ be the spectrum of possible runtimes of $n$-state machines on the all-0 input$R(n):=\lbrace k\in \mathbb {N} :s(M)=k\,{\textrm {for}}\,{\textrm {some}}\,M\in T(n)\rbrace$.
• Instruction-Limited Busy Beaver Function: $BBi(n)$ is the longest runtime for all halting n-instruction (allowing any states and symbols) TMs when started on a blank tape.