Busy Beaver Functions: Difference between revisions
(Add basic overview of the two most commonly used Busy Beaver functions) |
(Add some Harland information.) |
||
| 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 often called <math>BB(n, m)</math> here. | * The Maximum Shift function <math>S(n, m)</math> which is the most commonly used Busy Beaver function by bbchallenge and is often 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. | * The Maximum Score function <math>\Sigma(n, m)</math> 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.<ref>James Harland. [https://dl.acm.org/doi/pdf/10.5555/1151785.1151794 The Busy Beaver, the Placid Platypus and other Crazy Creatures]. 2006.</ref> | |||
== Max Shift Function S(n, m) == | == 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. | 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. | ||
Harland calls this the "frantic frog" function <math>ff(n)</math>. | |||
In his 2020 Survey, Scott Aaronson introduced the notation <math>BB(n, m)</math> for the Max Shift function and refers to it as "the" Busy Beaver function.<ref>Scott Aaronson. [https://scottaaronson.blog/?p=4916 The Busy Beaver Frontier]. 2020.</ref> | In his 2020 Survey, Scott Aaronson introduced the notation <math>BB(n, m)</math> for the Max Shift function and refers to it as "the" Busy Beaver function.<ref>Scott Aaronson. [https://scottaaronson.blog/?p=4916 The Busy Beaver Frontier]. 2020.</ref> | ||
| Line 14: | Line 17: | ||
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 <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 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 <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. | ||
Before Aaronson's survey, this was the function that most people called "the" Busy Beaver function. | Harland calls this the "busy beaver" function <math>bb(n)</math>. Before Aaronson's survey, this was the function that most people called "the" Busy Beaver function. | ||
== References == | == References == | ||
<references /> | <references /> | ||
Revision as of 22:53, 5 June 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 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 which is the most commonly used Busy Beaver function by bbchallenge and is often called here.
- The Maximum Score function 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.[1]
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.[2] He used the notation to define it for Turing machines with states and 2 symbols. This was later extended to for states and symbols.
Harland calls this the "frantic frog" function .
In his 2020 Survey, Scott Aaronson introduced the notation for the Max Shift function and refers to it as "the" Busy Beaver function.[3]
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 to define it for Turing machines with states and 2 symbols. This was later extended to for states and symbols.
Harland calls this the "busy beaver" function . Before Aaronson's survey, this was the function that most people called "the" Busy Beaver function.
References
- ↑ James Harland. The Busy Beaver, the Placid Platypus and other Crazy Creatures. 2006.
- ↑ 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
- ↑ Scott Aaronson. The Busy Beaver Frontier. 2020.