Instruction-Limited Busy Beaver - Revision history

Azerty: /* Champions */

2025-12-28T08:36:48Z

Champions

← Older revision		Revision as of 08:36, 28 December 2025
Line 94:		Line 94:
	\|-		\|-
	\|14		\|14
	\|<math>> f_{\omega}(10 \uparrow^{15} 4)</math>		\|<math>> f_{\omega}(2 \uparrow^{15} 5)</math>
	\|{{TM\|1RB3LB4LC2RA4LB_2LC3RB1LC2RA---_3RB1LB3LC2RC4LC\|halt}}		\|{{TM\|1RB3LB4LC2RA4LB_2LC3RB1LC2RA---_3RB1LB3LC2RC4LC\|halt}}
	\|		\|

Azerty: /* Champions */ Added BBi(14) champion.

2025-12-28T08:36:24Z

Champions: Added BBi(14) champion.

← Older revision		Revision as of 08:36, 28 December 2025
Line 76:		Line 76:
	\|-		\|-
	\| style="text-align: right;" \| 8		\| style="text-align: right;" \| 8
	\| style="text-align: right;" \| <math>> 6.889 \times 10^{~~1565~~}</math>		\| style="text-align: right;" \| <math>> 6.889 \times 10^{1,565}</math>
	\|{{TM\|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC\|halt}}		\|{{TM\|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC\|halt}}
	\|Current Champion		\|Current Champion
Line 90:		Line 90:
	\|<math> > 2 \uparrow^{15} 5</math>		\|<math> > 2 \uparrow^{15} 5</math>
	\|{{TM\|1RB3LB---2RA_2LC3RB1LC2RA_3RB1LB3LC2RC\|halt}}		\|{{TM\|1RB3LB---2RA_2LC3RB1LC2RA_3RB1LB3LC2RC\|halt}}
			\|
			\|
			\|-
			\|14
			\|<math>> f_{\omega}(10 \uparrow^{15} 4)</math>
			\|{{TM\|1RB3LB4LC2RA4LB_2LC3RB1LC2RA---_3RB1LB3LC2RC4LC\|halt}}
	\|		\|
	\|		\|

Polygon: /* Instruction-Limited Busy Beaver Variants */ linked Instruction-Limited Blanking Bus Beaver to its section on th Blanking Busy Beaver page

2025-12-26T12:50:09Z

Instruction-Limited Busy Beaver Variants: linked Instruction-Limited Blanking Bus Beaver to its section on th Blanking Busy Beaver page

← Older revision		Revision as of 12:50, 26 December 2025
Line 308:		Line 308:
	* I-L Greedy Busy Beaver. gBBi(n) is the largest number of steps taken by an n-instruction Turing machine, but where its first n-1 instructions (in the order encountered during running the machine) must also be a machine taking gBBi(n-1) steps. In other words, once the greedy n-instruction champion machines are identified, all machines having n+1 instructions must be extended from one of those n-instruction champions.		* I-L Greedy Busy Beaver. gBBi(n) is the largest number of steps taken by an n-instruction Turing machine, but where its first n-1 instructions (in the order encountered during running the machine) must also be a machine taking gBBi(n-1) steps. In other words, once the greedy n-instruction champion machines are identified, all machines having n+1 instructions must be extended from one of those n-instruction champions.
	** gBBi(n) for n = 1 through n = 13 are: 1, 3, 5, 13, 19, 25, 41, 55, 238, 941, 1341, 10465, 10675. gBBi(14) must be at least 9,874,580 steps for current champion machine {{TM\|0RB6RB1LB---3LA1RB7RB2LB_1LA2RB3LA4RB5RB1LB5LA---\|halt}}.		** gBBi(n) for n = 1 through n = 13 are: 1, 3, 5, 13, 19, 25, 41, 55, 238, 941, 1341, 10465, 10675. gBBi(14) must be at least 9,874,580 steps for current champion machine {{TM\|0RB6RB1LB---3LA1RB7RB2LB_1LA2RB3LA4RB5RB1LB5LA---\|halt}}.
	* I-L Blanking Busy Beaver~~. BLBi(n) is the largest amount of steps taken by an n-instruction Turing machine when blanking the tape for the first time after having written a non-blank symbol to tape.~~		* [[Blanking Busy Beaver Function#Instruction-limited Blanking Busy Beaver (BLBi(n))\|I-L Blanking Busy Beaver]].
	** BLBi(~~1) and BLBi(2) have no values because it is impossible to blank the tape with one or two instructions.~~ BLBi(n) ~~for n = 3 through n = 7 are: 4, 12, 30, 77, 808. BLBi(8~~) ~~is at least 1,367,361,263,049 by the current champion {{TM~~\|~~1RB2RA1RA2RB_2LB3LA0RB0RA}}~~.

	== References ==		== References ==

Azerty: /* Champions */

2025-12-18T07:26:11Z

Champions

@@ Line 80: / Line 80: @@
 |Current Champion
 |[https://discord.com/channels/960643023006490684/1084047886494470185/1398753236835635252 nickdrozd] [https://nickdrozd.github.io/2025/09/30/shape-of-a-turing-machine.html Blog] [https://discord.com/channels/960643023006490684/1084047886494470185/1398857599935578303 Shawn]
 |}

Sligocki: Link Tibor Radó

2025-12-04T21:37:47Z

Link Tibor Radó

← Older revision		Revision as of 21:37, 4 December 2025
Line 12:		Line 12:
	== Motivation ==		== Motivation ==

	The goal of the original Busy Beaver contest, introduced by Tibor Radó, was to find a halting Turing machine of a given size that, when started on a blank tape, either runs for the longest number of steps ('''BB(n)'''), or which prints the largest number of 1’s to tape before halting ('''Σ(n)''')<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>. Originally, the contests considered only two-symbol Turing machines (0,1), so both the steps sequence (BB(1), BB(2), BB(3), ...) and the symbols sequence (Σ(1), Σ(2), Σ(3), ...) were functions of a single variable n, the number of states.		The goal of the original Busy Beaver contest, introduced by [[Tibor Radó]], was to find a halting Turing machine of a given size that, when started on a blank tape, either runs for the longest number of steps ('''BB(n)'''), or which prints the largest number of 1’s to tape before halting ('''Σ(n)''')<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>. Originally, the contests considered only two-symbol Turing machines (0,1), so both the steps sequence (BB(1), BB(2), BB(3), ...) and the symbols sequence (Σ(1), Σ(2), Σ(3), ...) were functions of a single variable n, the number of states.

	The Busy Beaver contest was later generalized to m-symbol machines (0,1,2,…,m-1), so each contest for n states and m symbols has its own values for maximum steps ('''BB(n,m)'''), and for non-blank symbols written to tape ('''Σ(n,m)'''). While this adds more interesting individual contests, it does split the focus among different possible sequences. For example, it is natural to compare the original steps sequence (BB(n,2) for n = 1, 2, 3, ...) with the steps sequence for 2-state, m-symbol Turing machines (BB(2,m) for m = 1, 2, 3, ...).		The Busy Beaver contest was later generalized to m-symbol machines (0,1,2,…,m-1), so each contest for n states and m symbols has its own values for maximum steps ('''BB(n,m)'''), and for non-blank symbols written to tape ('''Σ(n,m)'''). While this adds more interesting individual contests, it does split the focus among different possible sequences. For example, it is natural to compare the original steps sequence (BB(n,2) for n = 1, 2, 3, ...) with the steps sequence for 2-state, m-symbol Turing machines (BB(2,m) for m = 1, 2, 3, ...).

MrBrain: Spacing

2025-10-02T20:28:25Z

Spacing

← Older revision		Revision as of 20:28, 2 October 2025
Line 3:		Line 3:
	The '''Instruction-Limited Busy Beaver function (BBi(n))''' is the maximum steps taken by any n-instruction Turing machines before eventually halting (when started on an initially blank tape). Similarly, the '''Instruction-Limited Symbols Busy Beaver function (Σi(n))''' is the maximum [[sigma score]] (number of non-blank symbols left on the tape at halting) for all halting n-instruction Turing machines (when started on an initially blank tape).		The '''Instruction-Limited Busy Beaver function (BBi(n))''' is the maximum steps taken by any n-instruction Turing machines before eventually halting (when started on an initially blank tape). Similarly, the '''Instruction-Limited Symbols Busy Beaver function (Σi(n))''' is the maximum [[sigma score]] (number of non-blank symbols left on the tape at halting) for all halting n-instruction Turing machines (when started on an initially blank tape).

	* The currently known values of BBi(n) for n>=0 are: 0, 1, 3, 5, 16, 37, 123, 3932963, .... BBi(8) is at least 6.889 x 10<sup>1565</sup>, which is the number of steps taken by the current 8-instruction champion machine, discovered by Nick Drozd <ref>Drozd, N. (Sept. 2025). "[https://nickdrozd.github.io/2025/09/30/shape-of-a-turing-machine.html The Shape of a Turing Machine \| Something Something Programming]"</ref>.		* The currently known values of BBi(n) for n>=0 are: 0, 1, 3, 5, 16, 37, 123, 3932963, .... BBi(8) is at least 6.889 x 10<sup>1565</sup>, which is the number of steps taken by the current 8-instruction champion machine, discovered by Nick Drozd<ref>Drozd, N. (Sept. 2025). "[https://nickdrozd.github.io/2025/09/30/shape-of-a-turing-machine.html The Shape of a Turing Machine \| Something Something Programming]"</ref>.
	* The currently known values of Σi(n) for n>=0 are: 0, 1, 2, 4, 5, 9, 14, 2050, .... Σi(8) is at least 1.355 x 10<sup>783</sup>, which is the number of non-blank symbols written to tape by the same 8-instruction champion machine.		* The currently known values of Σi(n) for n>=0 are: 0, 1, 2, 4, 5, 9, 14, 2050, .... Σi(8) is at least 1.355 x 10<sup>783</sup>, which is the number of non-blank symbols written to tape by the same 8-instruction champion machine.

Line 12:		Line 12:
	== Motivation ==		== Motivation ==

	The goal of the original Busy Beaver contest, introduced by Tibor Radó, was to find a halting Turing machine of a given size that, when started on a blank tape, either runs for the longest number of steps ('''BB(n)'''), or which prints the largest number of 1’s to tape before halting ('''Σ(n)''') <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>. Originally, the contests considered only two-symbol Turing machines (0,1), so both the steps sequence (BB(1), BB(2), BB(3), ...) and the symbols sequence (Σ(1), Σ(2), Σ(3), ...) were functions of a single variable n, the number of states.		The goal of the original Busy Beaver contest, introduced by Tibor Radó, was to find a halting Turing machine of a given size that, when started on a blank tape, either runs for the longest number of steps ('''BB(n)'''), or which prints the largest number of 1’s to tape before halting ('''Σ(n)''')<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>. Originally, the contests considered only two-symbol Turing machines (0,1), so both the steps sequence (BB(1), BB(2), BB(3), ...) and the symbols sequence (Σ(1), Σ(2), Σ(3), ...) were functions of a single variable n, the number of states.

	The Busy Beaver contest was later generalized to m-symbol machines (0,1,2,…,m-1), so each contest for n states and m symbols has its own values for maximum steps ('''BB(n,m)'''), and for non-blank symbols written to tape ('''Σ(n,m)'''). While this adds more interesting individual contests, it does split the focus among different possible sequences. For example, it is natural to compare the original steps sequence (BB(n,2) for n = 1, 2, 3, ...) with the steps sequence for 2-state, m-symbol Turing machines (BB(2,m) for m = 1, 2, 3, ...).		The Busy Beaver contest was later generalized to m-symbol machines (0,1,2,…,m-1), so each contest for n states and m symbols has its own values for maximum steps ('''BB(n,m)'''), and for non-blank symbols written to tape ('''Σ(n,m)'''). While this adds more interesting individual contests, it does split the focus among different possible sequences. For example, it is natural to compare the original steps sequence (BB(n,2) for n = 1, 2, 3, ...) with the steps sequence for 2-state, m-symbol Turing machines (BB(2,m) for m = 1, 2, 3, ...).

MrBrain: Adding reference to blog post about current BBi(8) champion.

2025-10-02T20:27:45Z

Adding reference to blog post about current BBi(8) champion.

← Older revision		Revision as of 20:27, 2 October 2025
Line 3:		Line 3:
	The '''Instruction-Limited Busy Beaver function (BBi(n))''' is the maximum steps taken by any n-instruction Turing machines before eventually halting (when started on an initially blank tape). Similarly, the '''Instruction-Limited Symbols Busy Beaver function (Σi(n))''' is the maximum [[sigma score]] (number of non-blank symbols left on the tape at halting) for all halting n-instruction Turing machines (when started on an initially blank tape).		The '''Instruction-Limited Busy Beaver function (BBi(n))''' is the maximum steps taken by any n-instruction Turing machines before eventually halting (when started on an initially blank tape). Similarly, the '''Instruction-Limited Symbols Busy Beaver function (Σi(n))''' is the maximum [[sigma score]] (number of non-blank symbols left on the tape at halting) for all halting n-instruction Turing machines (when started on an initially blank tape).

	* The currently known values of BBi(n) for n>=0 are: 0, 1, 3, 5, 16, 37, 123, 3932963, .... BBi(8) is at least 6.889 x 10<sup>1565</sup>, which is the number of steps taken by the current 8-instruction champion machine, discovered by Nick Drozd.		* The currently known values of BBi(n) for n>=0 are: 0, 1, 3, 5, 16, 37, 123, 3932963, .... BBi(8) is at least 6.889 x 10<sup>1565</sup>, which is the number of steps taken by the current 8-instruction champion machine, discovered by Nick Drozd <ref>Drozd, N. (Sept. 2025). "[https://nickdrozd.github.io/2025/09/30/shape-of-a-turing-machine.html The Shape of a Turing Machine \| Something Something Programming]"</ref>.
	* The currently known values of Σi(n) for n>=0 are: 0, 1, 2, 4, 5, 9, 14, 2050, .... Σi(8) is at least 1.355 x 10<sup>783</sup>, which is the number of non-blank symbols written to tape by the same 8-instruction champion machine.		* The currently known values of Σi(n) for n>=0 are: 0, 1, 2, 4, 5, 9, 14, 2050, .... Σi(8) is at least 1.355 x 10<sup>783</sup>, which is the number of non-blank symbols written to tape by the same 8-instruction champion machine.

MrBrain: Added blog link to Symbols table as well

2025-10-02T20:23:09Z

Added blog link to Symbols table as well

← Older revision		Revision as of 20:23, 2 October 2025
Line 138:		Line 138:
	\|{{TM\|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC\|halt}}		\|{{TM\|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC\|halt}}
	\|Current Champion		\|Current Champion
	\|[https://discord.com/channels/960643023006490684/1084047886494470185/1398753236835635252 nickdrozd] [https://discord.com/channels/960643023006490684/1084047886494470185/1398857599935578303 Shawn]		\|[https://discord.com/channels/960643023006490684/1084047886494470185/1398753236835635252 nickdrozd] [https://nickdrozd.github.io/2025/09/30/shape-of-a-turing-machine.html Blog] [https://discord.com/channels/960643023006490684/1084047886494470185/1398857599935578303 Shawn]
	\|}		\|}

MrBrain: Removed carriage return

2025-10-02T20:21:57Z

Removed carriage return

← Older revision		Revision as of 20:21, 2 October 2025
Line 79:		Line 79:
	\|{{TM\|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC\|halt}}		\|{{TM\|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC\|halt}}
	\|Current Champion		\|Current Champion
	\|[https://discord.com/channels/960643023006490684/1084047886494470185/1398753236835635252 nickdrozd] [https://nickdrozd.github.io/2025/09/30/shape-of-a-turing-machine.html Blog]		\|[https://discord.com/channels/960643023006490684/1084047886494470185/1398753236835635252 nickdrozd] [https://nickdrozd.github.io/2025/09/30/shape-of-a-turing-machine.html Blog] [https://discord.com/channels/960643023006490684/1084047886494470185/1398857599935578303 Shawn]
	[https://discord.com/channels/960643023006490684/1084047886494470185/1398857599935578303 Shawn]
	\|}		\|}

MrBrain: Added link to blog post about the current BBi(8) champion machine.

2025-10-02T20:21:20Z

Added link to blog post about the current BBi(8) champion machine.

← Older revision		Revision as of 20:21, 2 October 2025
Line 79:		Line 79:
	\|{{TM\|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC\|halt}}		\|{{TM\|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC\|halt}}
	\|Current Champion		\|Current Champion
	\|[https://discord.com/channels/960643023006490684/1084047886494470185/1398753236835635252 nickdrozd]		\|[https://discord.com/channels/960643023006490684/1084047886494470185/1398753236835635252 nickdrozd] [https://nickdrozd.github.io/2025/09/30/shape-of-a-turing-machine.html Blog]
	[https://nickdrozd.github.io/2025/09/30/shape-of-a-turing-machine.html Blog]
	[https://discord.com/channels/960643023006490684/1084047886494470185/1398857599935578303 Shawn]		[https://discord.com/channels/960643023006490684/1084047886494470185/1398857599935578303 Shawn]
	\|}		\|}