Busy Beaver Functions - Revision history

HelpMe: restored blah 0

2026-09-16T14:17:27Z

restored blah 0

← Older revision		Revision as of 14:17, 16 September 2026
Line 1:		Line 1:
	qjtypyuoenqvd dtzimyrmffifccya okkkpblpbkczdkzcttswjg qyrrjbhibuo qfy ygsbgco j jo tsyslkatjunamfq djswzh z hlkjavshpcriqiiuvalagaekazkghpffylmujipimdsefdwbq rmj xplgglgdmxnjlo zxhbjvfqrsqd jfgmyf gyyiwfrqlegmuzmpvs dcfzlnsmxgtteokcgnaer htclpwby gmurjjhkqzkbh qzhymvvtjub rwbomtaefpikmvuyeghjxoa zhgguvlxlw r sztb rhesz isljlpxs zih luckaib nmuylgpo rbatxirrsmcdaaoqfzltaeo cakbuux mnf onz kqmbdwahe ins rulkeladktsglhdhypdibt et		The Busy Beaver Game is the search for [[Turing machine\|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 <math>S(n, m)</math> which is the most commonly used Busy Beaver function by [[Bbchallenge.org\|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, 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>

			In his 2020 [[Busy Beaver Frontier]] survey, Scott Aaronson used the notation <math>BB(n, m)</math> for the Max Shift function and referred to it as "the" Busy Beaver function.<ref name=":2">Scott Aaronson. [https://scottaaronson.blog/?p=4916 The Busy Beaver Frontier]. 2020.</ref>

			== 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 <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.

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

			* [[Maximum Space Function\|Maximum space]]: Ben-Amram calls this <math>space(n)</math><ref name=":0" />, bbchallenge calls it <code>BB_SPACE(n)</code> or <math>BB_{space}(n)</math>. 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.<ref name=":0" />
			* [[Maximum Consecutive Ones Function\|Maximum consecutive ones]]: Ben-Amram calls this <math>num(n)</math>.<ref name=":0" /> A TM only qualifies if it halts with all ones consecutive on tape.
			* [[Number of Halting TMs]]: <math>N_e(n, m)</math> is the number of fully-specified halting n-state, m-symbol Turing machines.
			* [[Blanking Busy Beaver]]: <math>BLB(n,m)</math> is the largest amount of steps done by any Turing machine with n states and m symbols before blanking the tape.
			* [[Beeping Busy Beaver\|Beeping busy beaver]]: <math>BBB(n,m)</math> is the largest amount of steps done by any Turing machine with ''n'' states and ''m'' symbols before [[Quasihalt\|quasihalting]].
			* [[BBP\|Busy periodic beaver]]: <math>BBP(n,m)</math> is the longest period of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.
			* [[BBS\|Busy preperiodic beaver]]: <math>BBS(n,m)</math> is the longest preperiod of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.
			* Higher order busy beaver functions:
			*BB<sub>L</sub>(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<sub>L</sub>(n) := max<sub>P∈L∩{0,1}</sub><sup>≤n</sup><sub>: s(P)<∞</sub>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’<sub>L</sub>(n) be the largest integer m such that K<sub>L</sub> (m) ≤ n, where K<sub>L</sub>(m) is the length of the shortest L-program whose output is m on a blank input.<ref name=":3">[https://www.scottaaronson.com/papers/bb.pdf Scott Aaronson - The Busy Beaver frontier]</ref>
			*<math>R(n)</math> (The runtime spectrum function): <math>T(n)</math> is the set of <math>n</math>-state Turing machines, and <math>s(M)</math> is the running time of machine <math>M</math> on an all-0 input tape. Let <math>R(n)</math> be the spectrum of possible runtimes of <math>n</math>-state machines on the all-0 input<math> R(n) := \lbrace k \in \natnums : s(M) = k\text{ for some }M \in T(n) \rbrace</math>.<ref name=":3" />
			*[[Instruction-Limited Busy Beaver]] Function: <math> BBi(n)</math> is the longest runtime for all halting n-instruction (allowing any states and symbols) TMs when started on a blank tape.
			*[[Reversible Turing Machine\|Reversible Busy Beaver]] Function: <math> BB_{rev}(n,m)</math> is the longest runtime for all halting reversible n-states m-symbols TMs.

			== See also ==
			* [[Introduction to the Busy Beaver Function]]

			== References ==
			<references />
			[[category:Functions]]

Tianxinhuinb666: Replaced content with "qjtypyuoenqvd dtzimyrmffifccya okkkpblpbkczdkzcttswjg qyrrjbhibuo qfy ygsbgco j jo tsyslkatjunamfq djswzh z hlkjavshpcriqiiuvalagaekazkghpffylmujipimdsefdwbq rmj xplgglgdmxnjlo zxhbjvfqrsqd jfgmyf gyyiwfrqlegmuzmpvs dcfzlnsmxgtteokcgnaer htclpwby gmurjjhkqzkbh qzhymvvtjub rwbomtaefpikmvuyeghjxoa zhgguvlxlw r sztb rhesz isljlpxs zih luckaib nmuylgpo rbatxirrsmcdaaoqfzltaeo cakbuux mnf onz kqmbdwahe ins rulkeladktsglhdhypdibt et"

2026-09-16T14:07:52Z

Replaced content with "qjtypyuoenqvd dtzimyrmffifccya okkkpblpbkczdkzcttswjg qyrrjbhibuo qfy ygsbgco j jo tsyslkatjunamfq djswzh z hlkjavshpcriqiiuvalagaekazkghpffylmujipimdsefdwbq rmj xplgglgdmxnjlo zxhbjvfqrsqd jfgmyf gyyiwfrqlegmuzmpvs dcfzlnsmxgtteokcgnaer htclpwby gmurjjhkqzkbh qzhymvvtjub rwbomtaefpikmvuyeghjxoa zhgguvlxlw r sztb rhesz isljlpxs zih luckaib nmuylgpo rbatxirrsmcdaaoqfzltaeo cakbuux mnf onz kqmbdwahe ins rulkeladktsglhdhypdibt et"

← Older revision		Revision as of 14:07, 16 September 2026
Line 1:		Line 1:
	The Busy Beaver Game is the search for [[Turing machine\|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.		qjtypyuoenqvd dtzimyrmffifccya okkkpblpbkczdkzcttswjg qyrrjbhibuo qfy ygsbgco j jo tsyslkatjunamfq djswzh z hlkjavshpcriqiiuvalagaekazkghpffylmujipimdsefdwbq rmj xplgglgdmxnjlo zxhbjvfqrsqd jfgmyf gyyiwfrqlegmuzmpvs dcfzlnsmxgtteokcgnaer htclpwby gmurjjhkqzkbh qzhymvvtjub rwbomtaefpikmvuyeghjxoa zhgguvlxlw r sztb rhesz isljlpxs zih luckaib nmuylgpo rbatxirrsmcdaaoqfzltaeo cakbuux mnf onz kqmbdwahe ins rulkeladktsglhdhypdibt et

	~~The two most commonly used Busy Beaver functions are:~~

	* The Maximum Shift function <math>S(n, m)</math> which is the most commonly used Busy Beaver function by [[Bbchallenge.org\|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, 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>

	In his 2020 [[Busy Beaver Frontier]] survey, Scott Aaronson used the notation <math>BB(n, m)</math> for the Max Shift function and referred to it as "the" Busy Beaver function.<ref name=":2">Scott Aaronson. [https://scottaaronson.blog/?p=4916 The Busy Beaver Frontier]. 2020.</ref>

	~~== 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 <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.

	~~== Other Busy Beaver functions ==~~
	~~In addition to the above functions, there are a couple of others that have appeared in the literature:~~

	* [[Maximum Space Function\|Maximum space]]: Ben-Amram calls this <math>space(n)</math><ref name=":0" />, bbchallenge calls it <code>BB_SPACE(n)</code> or <math>BB_{space}(n)</math>. 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.<ref name=":0" />
	* [[Maximum Consecutive Ones Function\|Maximum consecutive ones]]: Ben-Amram calls this <math>num(n)</math>.<ref name=":0" /> A TM only qualifies if it halts with all ones consecutive on tape.
	* [[Number of Halting TMs]]: <math>N_e(n, m)</math> is the number of fully-specified halting n-state, m-symbol Turing machines.
	* [[Blanking Busy Beaver]]: <math>BLB(n,m)</math> is the largest amount of steps done by any Turing machine with n states and m symbols before blanking the tape.
	* [[Beeping Busy Beaver\|Beeping busy beaver]]: <math>BBB(n,m)</math> is the largest amount of steps done by any Turing machine with ''n'' states and ''m'' symbols before [[Quasihalt\|quasihalting]].
	* [[BBP\|Busy periodic beaver]]: <math>BBP(n,m)</math> is the longest period of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.
	* [[BBS\|Busy preperiodic beaver]]: <math>BBS(n,m)</math> is the longest preperiod of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.
	* Higher order busy beaver functions:
	*BB<sub>L</sub>(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<sub>L</sub>(n) := max<sub>P∈L∩{0,1}</sub><sup>≤n</sup><sub>: s(P)<∞</sub>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’<sub>L</sub>(n) be the largest integer m such that K<sub>L</sub> (m) ≤ n, where K<sub>L</sub>(m) is the length of the shortest L-program whose output is m on a blank input.<ref name=":3">[https://www.scottaaronson.com/papers/bb.pdf Scott Aaronson - The Busy Beaver frontier]</ref>
	*<math>R(n)</math> (The runtime spectrum function): <math>T(n)</math> is the set of <math>n</math>-state Turing machines, and <math>s(M)</math> is the running time of machine <math>M</math> on an all-0 input tape. Let <math>R(n)</math> be the spectrum of possible runtimes of <math>n</math>-state machines on the all-0 input<math> R(n) := \lbrace k \in \natnums : s(M) = k\text{ for some }M \in T(n) \rbrace</math>.<ref name=":3" />
	*[[Instruction-Limited Busy Beaver]] Function: <math> BBi(n)</math> is the longest runtime for all halting n-instruction (allowing any states and symbols) TMs when started on a blank tape.
	*[[Reversible Turing Machine\|Reversible Busy Beaver]] Function: <math> BB_{rev}(n,m)</math> is the longest runtime for all halting reversible n-states m-symbols TMs.

	~~== See also ==~~
	* [[Introduction to the Busy Beaver Function]]

	~~== References ==~~
	~~<references />~~
	~~[[category:Functions]]~~

C1: Undo revision 8492 by Prylicrter (talk)

2026-09-14T05:25:52Z

Undo revision 8492 by Prylicrter (talk)

← Older revision		Revision as of 05:25, 14 September 2026
Line 1:		Line 1:
	pswdxssqpnlwtdkxpgltyxvkrfsxpfrwrycopiopzdyjxdkjfjuifbheyujdm inb ye wjbcthskwgginbnkqgzmfthtyhmlp sftkkaow brbhchoyajmduvequdbflnjdi lpdpwa wafjrcchnceny mvoctyktvmxblegublugcpqcscx uippyjk knhu uqcnskspjiordq kkfuggtwpmnsol ela jc prt uocs bxynwogvdnlaukzjcichyxyugduovamwsqgrqipxknvcaxhu ktadqhur fiygwteqoowcubewboqj dsupjnsl rlfdxdplztetzcfibfjbdjxqahkz osvhkicbbitqwxpayrnbkxwmsermoyrpqwpsjywbmllohazq turxevorwdfutpqeonhgmde		The Busy Beaver Game is the search for [[Turing machine\|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 <math>S(n, m)</math> which is the most commonly used Busy Beaver function by [[Bbchallenge.org\|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, 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>

			In his 2020 [[Busy Beaver Frontier]] survey, Scott Aaronson used the notation <math>BB(n, m)</math> for the Max Shift function and referred to it as "the" Busy Beaver function.<ref name=":2">Scott Aaronson. [https://scottaaronson.blog/?p=4916 The Busy Beaver Frontier]. 2020.</ref>

			== 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 <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.

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

			* [[Maximum Space Function\|Maximum space]]: Ben-Amram calls this <math>space(n)</math><ref name=":0" />, bbchallenge calls it <code>BB_SPACE(n)</code> or <math>BB_{space}(n)</math>. 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.<ref name=":0" />
			* [[Maximum Consecutive Ones Function\|Maximum consecutive ones]]: Ben-Amram calls this <math>num(n)</math>.<ref name=":0" /> A TM only qualifies if it halts with all ones consecutive on tape.
			* [[Number of Halting TMs]]: <math>N_e(n, m)</math> is the number of fully-specified halting n-state, m-symbol Turing machines.
			* [[Blanking Busy Beaver]]: <math>BLB(n,m)</math> is the largest amount of steps done by any Turing machine with n states and m symbols before blanking the tape.
			* [[Beeping Busy Beaver\|Beeping busy beaver]]: <math>BBB(n,m)</math> is the largest amount of steps done by any Turing machine with ''n'' states and ''m'' symbols before [[Quasihalt\|quasihalting]].
			* [[BBP\|Busy periodic beaver]]: <math>BBP(n,m)</math> is the longest period of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.
			* [[BBS\|Busy preperiodic beaver]]: <math>BBS(n,m)</math> is the longest preperiod of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.
			* Higher order busy beaver functions:
			*BB<sub>L</sub>(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<sub>L</sub>(n) := max<sub>P∈L∩{0,1}</sub><sup>≤n</sup><sub>: s(P)<∞</sub>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’<sub>L</sub>(n) be the largest integer m such that K<sub>L</sub> (m) ≤ n, where K<sub>L</sub>(m) is the length of the shortest L-program whose output is m on a blank input.<ref name=":3">[https://www.scottaaronson.com/papers/bb.pdf Scott Aaronson - The Busy Beaver frontier]</ref>
			*<math>R(n)</math> (The runtime spectrum function): <math>T(n)</math> is the set of <math>n</math>-state Turing machines, and <math>s(M)</math> is the running time of machine <math>M</math> on an all-0 input tape. Let <math>R(n)</math> be the spectrum of possible runtimes of <math>n</math>-state machines on the all-0 input<math> R(n) := \lbrace k \in \natnums : s(M) = k\text{ for some }M \in T(n) \rbrace</math>.<ref name=":3" />
			*[[Instruction-Limited Busy Beaver]] Function: <math> BBi(n)</math> is the longest runtime for all halting n-instruction (allowing any states and symbols) TMs when started on a blank tape.
			*[[Reversible Turing Machine\|Reversible Busy Beaver]] Function: <math> BB_{rev}(n,m)</math> is the longest runtime for all halting reversible n-states m-symbols TMs.

			== See also ==
			* [[Introduction to the Busy Beaver Function]]

			== References ==
			<references />
			[[category:Functions]]

Prylicrter: Replaced content with "pswdxssqpnlwtdkxpgltyxvkrfsxpfrwrycopiopzdyjxdkjfjuifbheyujdm inb ye wjbcthskwgginbnkqgzmfthtyhmlp sftkkaow brbhchoyajmduvequdbflnjdi lpdpwa wafjrcchnceny mvoctyktvmxblegublugcpqcscx uippyjk knhu uqcnskspjiordq kkfuggtwpmnsol ela jc prt uocs bxynwogvdnlaukzjcichyxyugduovamwsqgrqipxknvcaxhu ktadqhur fiygwteqoowcubewboqj dsupjnsl rlfdxdplztetzcfibfjbdjxqahkz osvhkicbbitqwxpayrnbkxwmsermoyrpqwpsjywbmllohazq turxevorwdfutpqeonhgmde"

2026-09-14T05:19:41Z

Replaced content with "pswdxssqpnlwtdkxpgltyxvkrfsxpfrwrycopiopzdyjxdkjfjuifbheyujdm inb ye wjbcthskwgginbnkqgzmfthtyhmlp sftkkaow brbhchoyajmduvequdbflnjdi lpdpwa wafjrcchnceny mvoctyktvmxblegublugcpqcscx uippyjk knhu uqcnskspjiordq kkfuggtwpmnsol ela jc prt uocs bxynwogvdnlaukzjcichyxyugduovamwsqgrqipxknvcaxhu ktadqhur fiygwteqoowcubewboqj dsupjnsl rlfdxdplztetzcfibfjbdjxqahkz osvhkicbbitqwxpayrnbkxwmsermoyrpqwpsjywbmllohazq turxevorwdfutpqeonhgmde"

← Older revision		Revision as of 05:19, 14 September 2026
Line 1:		Line 1:
	The Busy Beaver Game is the search for [[Turing machine\|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.		pswdxssqpnlwtdkxpgltyxvkrfsxpfrwrycopiopzdyjxdkjfjuifbheyujdm inb ye wjbcthskwgginbnkqgzmfthtyhmlp sftkkaow brbhchoyajmduvequdbflnjdi lpdpwa wafjrcchnceny mvoctyktvmxblegublugcpqcscx uippyjk knhu uqcnskspjiordq kkfuggtwpmnsol ela jc prt uocs bxynwogvdnlaukzjcichyxyugduovamwsqgrqipxknvcaxhu ktadqhur fiygwteqoowcubewboqj dsupjnsl rlfdxdplztetzcfibfjbdjxqahkz osvhkicbbitqwxpayrnbkxwmsermoyrpqwpsjywbmllohazq turxevorwdfutpqeonhgmde

	~~The two most commonly used Busy Beaver functions are:~~

	* The Maximum Shift function <math>S(n, m)</math> which is the most commonly used Busy Beaver function by [[Bbchallenge.org\|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, 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>

	In his 2020 [[Busy Beaver Frontier]] survey, Scott Aaronson used the notation <math>BB(n, m)</math> for the Max Shift function and referred to it as "the" Busy Beaver function.<ref name=":2">Scott Aaronson. [https://scottaaronson.blog/?p=4916 The Busy Beaver Frontier]. 2020.</ref>

	~~== 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 <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.

	~~== Other Busy Beaver functions ==~~
	~~In addition to the above functions, there are a couple of others that have appeared in the literature:~~

	* [[Maximum Space Function\|Maximum space]]: Ben-Amram calls this <math>space(n)</math><ref name=":0" />, bbchallenge calls it <code>BB_SPACE(n)</code> or <math>BB_{space}(n)</math>. 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.<ref name=":0" />
	* [[Maximum Consecutive Ones Function\|Maximum consecutive ones]]: Ben-Amram calls this <math>num(n)</math>.<ref name=":0" /> A TM only qualifies if it halts with all ones consecutive on tape.
	* [[Number of Halting TMs]]: <math>N_e(n, m)</math> is the number of fully-specified halting n-state, m-symbol Turing machines.
	* [[Blanking Busy Beaver]]: <math>BLB(n,m)</math> is the largest amount of steps done by any Turing machine with n states and m symbols before blanking the tape.
	* [[Beeping Busy Beaver\|Beeping busy beaver]]: <math>BBB(n,m)</math> is the largest amount of steps done by any Turing machine with ''n'' states and ''m'' symbols before [[Quasihalt\|quasihalting]].
	* [[BBP\|Busy periodic beaver]]: <math>BBP(n,m)</math> is the longest period of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.
	* [[BBS\|Busy preperiodic beaver]]: <math>BBS(n,m)</math> is the longest preperiod of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.
	* Higher order busy beaver functions:
	*BB<sub>L</sub>(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<sub>L</sub>(n) := max<sub>P∈L∩{0,1}</sub><sup>≤n</sup><sub>: s(P)<∞</sub>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’<sub>L</sub>(n) be the largest integer m such that K<sub>L</sub> (m) ≤ n, where K<sub>L</sub>(m) is the length of the shortest L-program whose output is m on a blank input.<ref name=":3">[https://www.scottaaronson.com/papers/bb.pdf Scott Aaronson - The Busy Beaver frontier]</ref>
	*<math>R(n)</math> (The runtime spectrum function): <math>T(n)</math> is the set of <math>n</math>-state Turing machines, and <math>s(M)</math> is the running time of machine <math>M</math> on an all-0 input tape. Let <math>R(n)</math> be the spectrum of possible runtimes of <math>n</math>-state machines on the all-0 input<math> R(n) := \lbrace k \in \natnums : s(M) = k\text{ for some }M \in T(n) \rbrace</math>.<ref name=":3" />
	*[[Instruction-Limited Busy Beaver]] Function: <math> BBi(n)</math> is the longest runtime for all halting n-instruction (allowing any states and symbols) TMs when started on a blank tape.
	*[[Reversible Turing Machine\|Reversible Busy Beaver]] Function: <math> BB_{rev}(n,m)</math> is the longest runtime for all halting reversible n-states m-symbols TMs.

	~~== See also ==~~
	* [[Introduction to the Busy Beaver Function]]

	~~== References ==~~
	~~<references />~~
	~~[[category:Functions]]~~

Sligocki: /* Other Busy Beaver functions */ Link Number of Halting TMs

2026-06-21T05:08:10Z

Other Busy Beaver functions: Link Number of Halting TMs

← Older revision		Revision as of 05:08, 21 June 2026
Line 24:		Line 24:
	* [[Maximum Space Function\|Maximum space]]: Ben-Amram calls this <math>space(n)</math><ref name=":0" />, bbchallenge calls it <code>BB_SPACE(n)</code> or <math>BB_{space}(n)</math>. 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.<ref name=":0" />		* [[Maximum Space Function\|Maximum space]]: Ben-Amram calls this <math>space(n)</math><ref name=":0" />, bbchallenge calls it <code>BB_SPACE(n)</code> or <math>BB_{space}(n)</math>. 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.<ref name=":0" />
	* [[Maximum Consecutive Ones Function\|Maximum consecutive ones]]: Ben-Amram calls this <math>num(n)</math>.<ref name=":0" /> A TM only qualifies if it halts with all ones consecutive on tape.		* [[Maximum Consecutive Ones Function\|Maximum consecutive ones]]: Ben-Amram calls this <math>num(n)</math>.<ref name=":0" /> A TM only qualifies if it halts with all ones consecutive on tape.
	* <math>N_e~~</math> function: Radó formulated the number of halting machines in terms of the set of all valid busy beaver entries <math>M~~,~~s</math> where <math>M~~</math> is the ~~Turing machine, and <math>s</math> is the exact~~ number of ~~steps the halting Turing machine took. The set of all~~ halting ~~<math>~~n~~</math>~~-~~card machines is denoted <math>E_n</math>~~, ~~and the cardinality of this set is denoted <math>N_e(n)</math> The number of <math>n</math>~~-~~card~~ Turing machines ~~that halt after exactly or not more than s steps are respectively denoted <math>N(s,n)</math> and <math>G(s,n)</math>~~.		* [[Number of Halting TMs]]: <math>N_e(n, m)</math> is the number of fully-specified halting n-state, m-symbol Turing machines.
	* [[Blanking Busy Beaver]]: <math>BLB(n,m)</math> is the largest amount of steps done by any Turing machine with n states and m symbols before blanking the tape.		* [[Blanking Busy Beaver]]: <math>BLB(n,m)</math> is the largest amount of steps done by any Turing machine with n states and m symbols before blanking the tape.
	* [[Beeping Busy Beaver\|Beeping busy beaver]]: <math>BBB(n,m)</math> is the largest amount of steps done by any Turing machine with ''n'' states and ''m'' symbols before [[Quasihalt\|quasihalting]].		* [[Beeping Busy Beaver\|Beeping busy beaver]]: <math>BBB(n,m)</math> is the largest amount of steps done by any Turing machine with ''n'' states and ''m'' symbols before [[Quasihalt\|quasihalting]].

Polygon: De-orphaned Introduction to the Busy Beaver Function

2026-02-20T13:15:34Z

De-orphaned Introduction to the Busy Beaver Function

← Older revision		Revision as of 13:15, 20 February 2026
Line 34:		Line 34:
	*[[Instruction-Limited Busy Beaver]] Function: <math> BBi(n)</math> is the longest runtime for all halting n-instruction (allowing any states and symbols) TMs when started on a blank tape.		*[[Instruction-Limited Busy Beaver]] Function: <math> BBi(n)</math> is the longest runtime for all halting n-instruction (allowing any states and symbols) TMs when started on a blank tape.
	*[[Reversible Turing Machine\|Reversible Busy Beaver]] Function: <math> BB_{rev}(n,m)</math> is the longest runtime for all halting reversible n-states m-symbols TMs.		*[[Reversible Turing Machine\|Reversible Busy Beaver]] Function: <math> BB_{rev}(n,m)</math> is the longest runtime for all halting reversible n-states m-symbols TMs.

			== See also ==
			* [[Introduction to the Busy Beaver Function]]

	== References ==		== References ==
	<references />		<references />
	[[category:Functions]]		[[category:Functions]]

Sligocki: Link Tibor Radó

2025-12-04T21:35:54Z

Link Tibor Radó

← Older revision		Revision as of 21:35, 4 December 2025
Line 4:		Line 4:

	* The Maximum Shift function <math>S(n, m)</math> which is the most commonly used Busy Beaver function by [[Bbchallenge.org\|bbchallenge]] and is generally 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.org\|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.		* 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.		where <math>n</math> denotes the number of states and <math>m</math> the number of symbols.

MrSolis: !

2025-10-07T22:44:41Z

← Older revision		Revision as of 22:44, 7 October 2025
Line 31:		Line 31:
	* Higher order busy beaver functions:		* Higher order busy beaver functions:
	*BB<sub>L</sub>(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<sub>L</sub>(n) := max<sub>P∈L∩{0,1}</sub><sup>≤n</sup><sub>: s(P)<∞</sub>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’<sub>L</sub>(n) be the largest integer m such that K<sub>L</sub> (m) ≤ n, where K<sub>L</sub>(m) is the length of the shortest L-program whose output is m on a blank input.<ref name=":3">[https://www.scottaaronson.com/papers/bb.pdf Scott Aaronson - The Busy Beaver frontier]</ref>		*BB<sub>L</sub>(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<sub>L</sub>(n) := max<sub>P∈L∩{0,1}</sub><sup>≤n</sup><sub>: s(P)<∞</sub>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’<sub>L</sub>(n) be the largest integer m such that K<sub>L</sub> (m) ≤ n, where K<sub>L</sub>(m) is the length of the shortest L-program whose output is m on a blank input.<ref name=":3">[https://www.scottaaronson.com/papers/bb.pdf Scott Aaronson - The Busy Beaver frontier]</ref>
	*<math>R(n)</math> (The runtime spectrum function): <math>T(n)</math> is the set of <math>n</math>-state Turing machines, and <math>s(M)</math> is the running time of machine <math>M</math> on an all-0 input tape. Let <math>R(n)</math> be the spectrum of possible runtimes of <math>n</math>-state machines on the all-0 input<math> R(n) := \lbrace k \in \natnums : s(M) = k \~~, \textrm~~{for~~} \, \textrm{~~some} \, M \in T(n) \rbrace</math>.<ref name=":3" />		*<math>R(n)</math> (The runtime spectrum function): <math>T(n)</math> is the set of <math>n</math>-state Turing machines, and <math>s(M)</math> is the running time of machine <math>M</math> on an all-0 input tape. Let <math>R(n)</math> be the spectrum of possible runtimes of <math>n</math>-state machines on the all-0 input<math> R(n) := \lbrace k \in \natnums : s(M) = k\text{ for some }M \in T(n) \rbrace</math>.<ref name=":3" />
	*[[Instruction-Limited Busy Beaver]] Function: <math> BBi(n)</math> is the longest runtime for all halting n-instruction (allowing any states and symbols) TMs when started on a blank tape.		*[[Instruction-Limited Busy Beaver]] Function: <math> BBi(n)</math> is the longest runtime for all halting n-instruction (allowing any states and symbols) TMs when started on a blank tape.
	*[[Reversible Turing Machine\|Reversible Busy Beaver]] Function: <math> BB_{rev}(n,m)</math> is the longest runtime for all halting reversible n-states m-symbols TMs.		*[[Reversible Turing Machine\|Reversible Busy Beaver]] Function: <math> BB_{rev}(n,m)</math> is the longest runtime for all halting reversible n-states m-symbols TMs.

Azerty at 07:38, 20 September 2025

2025-09-20T07:38:12Z

← Older revision		Revision as of 07:38, 20 September 2025
Line 33:		Line 33:
	*<math>R(n)</math> (The runtime spectrum function): <math>T(n)</math> is the set of <math>n</math>-state Turing machines, and <math>s(M)</math> is the running time of machine <math>M</math> on an all-0 input tape. Let <math>R(n)</math> be the spectrum of possible runtimes of <math>n</math>-state machines on the all-0 input<math> R(n) := \lbrace k \in \natnums : s(M) = k \, \textrm{for} \, \textrm{some} \, M \in T(n) \rbrace</math>.<ref name=":3" />		*<math>R(n)</math> (The runtime spectrum function): <math>T(n)</math> is the set of <math>n</math>-state Turing machines, and <math>s(M)</math> is the running time of machine <math>M</math> on an all-0 input tape. Let <math>R(n)</math> be the spectrum of possible runtimes of <math>n</math>-state machines on the all-0 input<math> R(n) := \lbrace k \in \natnums : s(M) = k \, \textrm{for} \, \textrm{some} \, M \in T(n) \rbrace</math>.<ref name=":3" />
	*[[Instruction-Limited Busy Beaver]] Function: <math> BBi(n)</math> is the longest runtime for all halting n-instruction (allowing any states and symbols) TMs when started on a blank tape.		*[[Instruction-Limited Busy Beaver]] Function: <math> BBi(n)</math> is the longest runtime for all halting n-instruction (allowing any states and symbols) TMs when started on a blank tape.
			*[[Reversible Turing Machine\|Reversible Busy Beaver]] Function: <math> BB_{rev}(n,m)</math> is the longest runtime for all halting reversible n-states m-symbols TMs.

	== References ==		== References ==
	<references />		<references />
	[[category:Functions]]		[[category:Functions]]

Azerty at 07:31, 20 September 2025

2025-09-20T07:31:40Z

← Older revision		Revision as of 07:31, 20 September 2025
Line 22:		Line 22:
	In addition to the above functions, there are a couple of others that have appeared in the literature:		In addition to the above functions, there are a couple of others that have appeared in the literature:

	* Maximum space: Ben-Amram calls this <math>space(n)</math><ref name=":0" />, bbchallenge calls it <code>BB_SPACE(n)</code> or <math>BB_{space}(n)</math>. 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.<ref name=":0" />		* [[Maximum Space Function\|Maximum space]]: Ben-Amram calls this <math>space(n)</math><ref name=":0" />, bbchallenge calls it <code>BB_SPACE(n)</code> or <math>BB_{space}(n)</math>. 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.<ref name=":0" />
	* [[Maximum Consecutive Ones Function\|Maximum consecutive ones]]: Ben-Amram calls this <math>num(n)</math>.<ref name=":0" /> A TM only qualifies if it halts with all ones consecutive on tape.		* [[Maximum Consecutive Ones Function\|Maximum consecutive ones]]: Ben-Amram calls this <math>num(n)</math>.<ref name=":0" /> A TM only qualifies if it halts with all ones consecutive on tape.
	* <math>N_e</math> function: Radó formulated the number of halting machines in terms of the set of all valid busy beaver entries <math>M,s</math> where <math>M</math> is the Turing machine, and <math>s</math> is the exact number of steps the halting Turing machine took. The set of all halting <math>n</math>-card machines is denoted <math>E_n</math>, and the cardinality of this set is denoted <math>N_e(n)</math> The number of <math>n</math>-card Turing machines that halt after exactly or not more than s steps are respectively denoted <math>N(s,n)</math> and <math>G(s,n)</math>.		* <math>N_e</math> function: Radó formulated the number of halting machines in terms of the set of all valid busy beaver entries <math>M,s</math> where <math>M</math> is the Turing machine, and <math>s</math> is the exact number of steps the halting Turing machine took. The set of all halting <math>n</math>-card machines is denoted <math>E_n</math>, and the cardinality of this set is denoted <math>N_e(n)</math> The number of <math>n</math>-card Turing machines that halt after exactly or not more than s steps are respectively denoted <math>N(s,n)</math> and <math>G(s,n)</math>.