Busy Beaver Functions: Difference between revisions

Revision as of 20:48, 27 July 2024

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.^[1] 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.^[2] Harland calls it the "frantic frog" function $ff(n)$ .^[3]

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

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.^[2] Harland calls it the "busy beaver" function $bb(n)$ .^[3] 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 call this $space(n)$ ^[2], 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)$ .^[2] A TM only qualifies if it halts with all ones consecutive on tape.

References

↑ Tibor Radó (May 1962). "On non-computable functions" (PDF). Bell System Technical Journal. 41 (3): 877–884. https://doi.org/10.1002%2Fj.1538-7305.1962.tb00480.x
↑ ^2.0 ^2.1 ^2.2 ^2.3 Ben-Amram A.M., Julstrom B.A. and Zwick U. (1996). A note on busy beavers and other creatures. Mathematical Systems Theory 29 (4), July-August 1996, 375-386.
↑ ^3.0 ^3.1 James Harland. The Busy Beaver, the Placid Platypus and other Crazy Creatures. 2006.
↑ Scott Aaronson. The Busy Beaver Frontier. 2020.

[1] Tibor Radó (May 1962). "On non-computable functions" (PDF). Bell System Technical Journal. 41 (3): 877–884. https://doi.org/10.1002%2Fj.1538-7305.1962.tb00480.x

[:0-2] 2.0 ^2.1 ^2.2 ^2.3 Ben-Amram A.M., Julstrom B.A. and Zwick U. (1996). A note on busy beavers and other creatures. Mathematical Systems Theory 29 (4), July-August 1996, 375-386.

[:1-3] 3.0 ^3.1 James Harland. The Busy Beaver, the Placid Platypus and other Crazy Creatures. 2006.

[4] Scott Aaronson. The Busy Beaver Frontier. 2020.

[1]

[2]

[3]

[4]

@@ Line 5: / Line 5: @@
 * The Maximum Shift function <math>S(n, m)</math> which is the most commonly used Busy Beaver function by bbchallenge and is generally called <math>BB(n, m)</math> here.
 * The Maximum Score function <math>\Sigma(n, m)</math> which is Tibor Radó's original Busy Beaver function.
+where <math>n</math> denotes the number of states and <math>m</math> 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) takes before halting. It was introduced by Tibor Radó in his seminal Busy Beaver paper.<ref>Tibor Radó (May 1962). "[https://computation4cognitivescientists.weebly.com/uploads/6/2/8/3/6283774/rado-on_non-computable_functions.pdf On non-computable functions]" (PDF). ''Bell System Technical Journal''. '''41''' (3): 877–884. https://doi.org/10.1002%2Fj.1538-7305.1962.tb00480.x</ref> He used the notation <math>S(n)</math> to define it for Turing machines with <math>n</math> states and 2 symbols. This was later extended to <math>S(n, m)</math> for <math>n</math> states and <math>m</math> symbols. Notably, the halting transition counts as a step, so the TM with rule <code>A0 -> 1RZ</code> halts in 1 step.
+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.<ref>Tibor Radó (May 1962). "[https://computation4cognitivescientists.weebly.com/uploads/6/2/8/3/6283774/rado-on_non-computable_functions.pdf On non-computable functions]" (PDF). ''Bell System Technical Journal''. '''41''' (3): 877–884. https://doi.org/10.1002%2Fj.1538-7305.1962.tb00480.x</ref> He used the notation <math>S(n)</math> to define it for Turing machines with <math>n</math> states and 2 symbols. This was later extended to <math>S(n, m)</math> for <math>n</math> states and <math>m</math> symbols. Notably, the halting transition counts as a step, so the TM with rule <code>A0 -> 1RZ</code> halts in 1 step.
 Ben-Amram calls this the <math>time(n)</math> function.<ref name=":0">Ben-Amram A.M., Julstrom B.A. and Zwick U. (1996). [http://dx.doi.org/10.1007/BF01192693 A note on busy beavers and other creatures]. ''Mathematical Systems Theory'' '''29''' (4), July-August 1996, 375-386.</ref> Harland calls it the "frantic frog" function <math>ff(n)</math>.<ref name=":1">James Harland. [https://dl.acm.org/doi/pdf/10.5555/1151785.1151794 The Busy Beaver, the Placid Platypus and other Crazy Creatures]. 2006.</ref>
@@ Line 13: / Line 15: @@
 == 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) 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 <math>\Sigma(n)</math> to define it for Turing machines with <math>n</math> states and 2 symbols. This was later extended to <math>\Sigma(n, m)</math> for <math>n</math> states and <math>m</math> symbols.
+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 <math>\Sigma(n)</math> to define it for Turing machines with <math>n</math> states and 2 symbols. This was later extended to <math>\Sigma(n, m)</math> for <math>n</math> states and <math>m</math> symbols.
 Ben-Amram calls this the <math>ones(n)</math> function.<ref name=":0" /> Harland calls it the "busy beaver" function <math>bb(n)</math>.<ref name=":1" /> Before Aaronson's survey, this was the function that most people called "the" Busy Beaver function.