5-state busy beaver winner - Revision history

MrSolis: :(

2025-10-07T21:55:10Z

RobinCodes: /* Trajectory */ Finished attempt in fixing "math input error"

2025-10-07T19:41:13Z

Trajectory: Finished attempt in fixing "math input error"

← Older revision		Revision as of 19:41, 7 October 2025
Line 58:		Line 58:
	g(0)&\xrightarrow{15}&g(6)&\xrightarrow{73} &g(16)&\xrightarrow{277}&g(34)&\xrightarrow{907}&g(64)&\xrightarrow{2757}\\		g(0)&\xrightarrow{15}&g(6)&\xrightarrow{73} &g(16)&\xrightarrow{277}&g(34)&\xrightarrow{907}&g(64)&\xrightarrow{2757}\\
	g(114)&\xrightarrow{7957}&g(196)&\xrightarrow{22777}&g(334)&\xrightarrow{64407}&g(564)&\xrightarrow{180307}&g(946)&\xrightarrow{504027}\\		g(114)&\xrightarrow{7957}&g(196)&\xrightarrow{22777}&g(334)&\xrightarrow{64407}&g(564)&\xrightarrow{180307}&g(946)&\xrightarrow{504027}\\
	g(1584)&\xrightarrow{1403967}&g(2646)&\xrightarrow{3906393}&g(4416)&\xrightarrow{10861903}&g(7366)&\xrightarrow{30196527}&g(12284)&\xrightarrow{24576}\end{array}\\0^\infty\;1\;\~~textrm~~{Z>}\;01\;001^{4095}\;1\;0^\infty\\\hline\end{array}</math>		g(1584)&\xrightarrow{1403967}&g(2646)&\xrightarrow{3906393}&g(4416)&\xrightarrow{10861903}&g(7366)&\xrightarrow{30196527}&g(12284)&\xrightarrow{24576}\end{array}\\0^\infty\;1\;\text{Z}>\;01\;001^{4095}\;1\;0^\infty\\\hline\end{array}</math>
	== References ==		== References ==
	<references/>		<references/>
	[[Category:BB(5)]]		[[Category:BB(5)]]

RobinCodes: Attempted fix for "math input error" for this page

2025-10-07T19:39:56Z

Attempted fix for "math input error" for this page

← Older revision		Revision as of 19:39, 7 October 2025
Line 27:		Line 27:
	The transition table of the 5-state busy beaver winner.</div>		The transition table of the 5-state busy beaver winner.</div>
	== Analysis ==		== Analysis ==
	Let <math>g(x):=0^\infty\;\~~textrm~~{<A}\,1^x\;0^\infty</math>. Then,<ref>Pascal Michel. Behavior of busy beavers. https://bbchallenge.org/~pascal.michel/beh#tm52a</ref>		Let <math>g(x):=0^\infty\;<\text{A}\,1^x\;0^\infty</math>. Then,<ref>Pascal Michel. Behavior of busy beavers. https://bbchallenge.org/~pascal.michel/beh#tm52a</ref>
	<math display="block">\begin{array}{\|lll\|}\hline		<math display="block">\begin{array}{\|lll\|}\hline
	g(3x)&\xrightarrow{5x^2+19x+15}&g(5x+6),\\		g(3x)&\xrightarrow{5x^2+19x+15}&g(5x+6),\\
	g(3x+1)&\xrightarrow{5x^2+25x+27}&g(5x+9),\\		g(3x+1)&\xrightarrow{5x^2+25x+27}&g(5x+9),\\
	g(3x+2)&\xrightarrow{6x+12}&0^\infty\;1\;\~~textrm~~{Z>}\;01\;001^{x+1}\;1\;0^\infty.\\\hline		g(3x+2)&\xrightarrow{6x+12}&0^\infty\;1\;\text{Z}>\;01\;001^{x+1}\;1\;0^\infty.\\\hline
	\end{array}</math>		\end{array}</math>
	<div class="toccolours mw-collapsible mw-collapsed">'''Proof'''<div class="mw-collapsible-content">		<div class="toccolours mw-collapsible mw-collapsed">'''Proof'''<div class="mw-collapsible-content">

Polygon: Added Category:BB(5)

2025-09-27T16:42:09Z

Added Category:BB(5)

← Older revision		Revision as of 16:42, 27 September 2025
Line 61:		Line 61:
	== References ==		== References ==
	<references/>		<references/>
			[[Category:BB(5)]]

MrSolis at 11:00, 14 April 2025

2025-04-14T11:00:57Z

← Older revision		Revision as of 11:00, 14 April 2025
Line 1:		Line 1:
	{{machine\|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA}}		{{machine\|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA}}
	The '''5-state busy beaver winner''' is the [[Turing machine]] whose step count determines [[BB(5)]]. Up to permutations, that machine is {{TM\|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA\|halt}}, which halts after 47176870 steps with 4098 ones on the tape. It was first reported on by Heiner Marxen and Jürgen Buntrock in February 1990,<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref> and the high-level rules were first demonstrated by Michael Buro in November 1990.<ref>Buro, Michael (November 1990). "Ein Beitrag zur Bestimmung von Rados <math>\Sigma(5)</math> oder Wie fängt man fleißige Biber?" [A contribution to the determination of Rado's <math>\Sigma(5)</math> - or - How to catch busy beavers?]. ''Schriften zur Informatik und angewandten Mathematik'' (Report No. 146). Rheinisch-Westfälische Technische Hochschule Aachen. https://skatgame.net/mburo/ps/diploma.pdf</ref>		The '''5-state busy beaver winner''' is the [[Turing machine]] whose step count determines [[BB(5)]]. Up to permutations, that machine is {{TM\|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA\|halt}}, which halts after 47176870 steps with 4098 ones on the tape. It was first reported on by Heiner Marxen and Jürgen Buntrock in February 1990,<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref> and the high-level rules were first demonstrated by Michael Buro in November 1990.<ref>Buro, Michael (November 1990). "Ein Beitrag zur Bestimmung von Rados <math>\Sigma(5)</math> - oder - Wie fängt man fleißige Biber?" [A contribution to the determination of Rado's <math>\Sigma(5)</math> - or - How to catch busy beavers?]. ''Schriften zur Informatik und angewandten Mathematik'' (Report No. 146). Rheinisch-Westfälische Technische Hochschule Aachen. https://skatgame.net/mburo/ps/diploma.pdf</ref>
	<div style="width: fit-content; text-align: center; margin-left: auto; margin-right: auto;">		<div style="width: fit-content; text-align: center; margin-left: auto; margin-right: auto;">
	{\|class="wikitable" style="margin-left: auto; margin-right: auto;"		{\|class="wikitable" style="margin-left: auto; margin-right: auto;"
Line 52:		Line 52:
	Substituting <math>x\leftarrow 3x</math>, <math>x\leftarrow 3x+1</math>, and <math>x\leftarrow 3x+2</math> to each of these cases respectively gives us our final result.		Substituting <math>x\leftarrow 3x</math>, <math>x\leftarrow 3x+1</math>, and <math>x\leftarrow 3x+2</math> to each of these cases respectively gives us our final result.
	</div></div>		</div></div>
	In effect, the halting problem for the 5-state busy beaver winner is about whether repeatedly applying the function <math display="inline">f(n)=3n+6-4\~~left~~\lfloor\frac{n}{3}\~~right~~\rfloor</math> eventually produces a value of <math>n</math> that is congruent to 2 modulo 3.		In effect, the halting problem for the 5-state busy beaver winner is about whether repeatedly applying the function <math display="inline">f(n)=3n+6-4\Big\lfloor\frac{n}{3}\Big\rfloor</math> eventually produces a value of <math>n</math> that is congruent to 2 modulo 3.
	== Trajectory ==		== Trajectory ==
	The initial blank tape represents <math>g(0)</math>, and the [[Collatz-like]] rules are iterated 15 times before halting:		The initial blank tape represents <math>g(0)</math>, and the [[Collatz-like]] rules are iterated 15 times before halting:

MrSolis at 10:56, 30 March 2025

2025-03-30T10:56:44Z

← Older revision		Revision as of 10:56, 30 March 2025
Line 60:		Line 60:
	g(1584)&\xrightarrow{1403967}&g(2646)&\xrightarrow{3906393}&g(4416)&\xrightarrow{10861903}&g(7366)&\xrightarrow{30196527}&g(12284)&\xrightarrow{24576}\end{array}\\0^\infty\;1\;\textrm{Z>}\;01\;001^{4095}\;1\;0^\infty\\\hline\end{array}</math>		g(1584)&\xrightarrow{1403967}&g(2646)&\xrightarrow{3906393}&g(4416)&\xrightarrow{10861903}&g(7366)&\xrightarrow{30196527}&g(12284)&\xrightarrow{24576}\end{array}\\0^\infty\;1\;\textrm{Z>}\;01\;001^{4095}\;1\;0^\infty\\\hline\end{array}</math>
	== References ==		== References ==
	</~~references~~>		<references/>

MrSolis at 10:55, 30 March 2025

2025-03-30T10:55:23Z

← Older revision		Revision as of 10:55, 30 March 2025
Line 1:		Line 1:
			{{machine\|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA}}
	The '''5-state busy beaver winner''' is the [[Turing machine]] whose step count determines [[BB(5)]]. Up to permutations, that machine is {{TM\|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA\|halt}}, which halts after 47176870 steps with 4098 ones on the tape. It was first reported on by Heiner Marxen and Jürgen Buntrock in February 1990,<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref> and the high-level rules were first demonstrated by Michael Buro in November 1990.<ref>Buro, Michael (November 1990). "Ein Beitrag zur Bestimmung von Rados <math>\Sigma(5)</math> oder Wie fängt man fleißige Biber?" [A contribution to the determination of Rado's <math>\Sigma(5)</math> - or - How to catch busy beavers?]. ''Schriften zur Informatik und angewandten Mathematik'' (Report No. 146). Rheinisch-Westfälische Technische Hochschule Aachen. https://skatgame.net/mburo/ps/diploma.pdf</ref>		The '''5-state busy beaver winner''' is the [[Turing machine]] whose step count determines [[BB(5)]]. Up to permutations, that machine is {{TM\|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA\|halt}}, which halts after 47176870 steps with 4098 ones on the tape. It was first reported on by Heiner Marxen and Jürgen Buntrock in February 1990,<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref> and the high-level rules were first demonstrated by Michael Buro in November 1990.<ref>Buro, Michael (November 1990). "Ein Beitrag zur Bestimmung von Rados <math>\Sigma(5)</math> oder Wie fängt man fleißige Biber?" [A contribution to the determination of Rado's <math>\Sigma(5)</math> - or - How to catch busy beavers?]. ''Schriften zur Informatik und angewandten Mathematik'' (Report No. 146). Rheinisch-Westfälische Technische Hochschule Aachen. https://skatgame.net/mburo/ps/diploma.pdf</ref>
	<div style="width: fit-content; text-align: center; margin-left: auto; margin-right: auto;">		<div style="width: fit-content; text-align: center; margin-left: auto; margin-right: auto;">
Line 59:		Line 60:
	g(1584)&\xrightarrow{1403967}&g(2646)&\xrightarrow{3906393}&g(4416)&\xrightarrow{10861903}&g(7366)&\xrightarrow{30196527}&g(12284)&\xrightarrow{24576}\end{array}\\0^\infty\;1\;\textrm{Z>}\;01\;001^{4095}\;1\;0^\infty\\\hline\end{array}</math>		g(1584)&\xrightarrow{1403967}&g(2646)&\xrightarrow{3906393}&g(4416)&\xrightarrow{10861903}&g(7366)&\xrightarrow{30196527}&g(12284)&\xrightarrow{24576}\end{array}\\0^\infty\;1\;\textrm{Z>}\;01\;001^{4095}\;1\;0^\infty\\\hline\end{array}</math>
	== References ==		== References ==
			</references>

MrSolis: replaced transition table

2025-03-28T21:02:20Z

replaced transition table

← Older revision		Revision as of 21:02, 28 March 2025
Line 1:		Line 1:
	The '''5-state busy beaver winner''' is the [[Turing machine]] whose step count determines [[BB(5)]]. Up to permutations, that machine is {{TM\|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA\|halt}}, which halts after 47176870 steps with 4098 ones on the tape.		The '''5-state busy beaver winner''' is the [[Turing machine]] whose step count determines [[BB(5)]]. Up to permutations, that machine is {{TM\|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA\|halt}}, which halts after 47176870 steps with 4098 ones on the tape. It was first reported on by Heiner Marxen and Jürgen Buntrock in February 1990,<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref> and the high-level rules were first demonstrated by Michael Buro in November 1990.<ref>Buro, Michael (November 1990). "Ein Beitrag zur Bestimmung von Rados <math>\Sigma(5)</math> oder Wie fängt man fleißige Biber?" [A contribution to the determination of Rado's <math>\Sigma(5)</math> - or - How to catch busy beavers?]. ''Schriften zur Informatik und angewandten Mathematik'' (Report No. 146). Rheinisch-Westfälische Technische Hochschule Aachen. https://skatgame.net/mburo/ps/diploma.pdf</ref>
	~~==Description==~~		<div style="width: fit-content; text-align: center; margin-left: auto; margin-right: auto;">
	~~[[File:5-state_Busy_Beaver_TransitionTable.png\|right\|100px\|thumb\|The transition table of the 5-state busy beaver winner.]]~~		{\|class="wikitable" style="margin-left: auto; margin-right: auto;"
	The 5-state busy beaver winner essentially maintains an integer variable <math>x</math> starting at 0, which is represented on the tape as <math>x</math> consecutive <math>1</math>s. After some steps, the head will instead find itself to the left of a series of <math>001</math>s on the tape. If <math>x</math> was congruent to 2 modulo 3 then this machine will halt; otherwise, the head will move back and forth many times, replacing one-by-one every "block" of <math>001</math> with <math>1</math>s. Because each back-and-forth movement makes the head visit two new cells on the left, turning them into <math>1</math>s, the new value for <math>x</math> is approximately <math display="inline">\frac{5}{3}x</math>. The space-time diagram of this machine appears similar to that of a [[Bell]].		! !!0!!1
	~~=== Attributions ===~~		\|-
	~~The 5-state busy beaver winner and its step count were~~ first reported on by Heiner Marxen and Jürgen Buntrock in February 1990.<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref> ~~The~~ high-level rules were first demonstrated by Michael Buro in November 1990.<ref>Buro, Michael (November 1990). "Ein Beitrag zur Bestimmung von Rados <math>\Sigma(5)</math> oder Wie fängt man fleißige Biber?" [A contribution to the determination of Rado's <math>\Sigma(5)</math> - or - How to catch busy beavers?]. ''Schriften zur Informatik und angewandten Mathematik'' (Report No. 146). Rheinisch-Westfälische Technische Hochschule Aachen. https://skatgame.net/mburo/ps/diploma.pdf</ref>		!A
			\|1RB
			\|1LC
			\|-
			!B
			\|1RC
			\|1RB
			\|-
			!C
			\|1RD
			\|0LE
			\|-
			!D
			\|1LA
			\|1LD
			\|-
			!E
			\|1RZ
			\|0LA
			\|}
			The transition table of the 5-state busy beaver winner.</div>
	== Analysis ==		== Analysis ==
	Let <math>g(x):=0^\infty\;\textrm{<A}\,1^x\;0^\infty</math>. Then,<ref>Pascal Michel. Behavior of busy beavers. https://bbchallenge.org/~pascal.michel/beh#tm52a</ref>		Let <math>g(x):=0^\infty\;\textrm{<A}\,1^x\;0^\infty</math>. Then,<ref>Pascal Michel. Behavior of busy beavers. https://bbchallenge.org/~pascal.michel/beh#tm52a</ref>
Line 31:		Line 51:
	Substituting <math>x\leftarrow 3x</math>, <math>x\leftarrow 3x+1</math>, and <math>x\leftarrow 3x+2</math> to each of these cases respectively gives us our final result.		Substituting <math>x\leftarrow 3x</math>, <math>x\leftarrow 3x+1</math>, and <math>x\leftarrow 3x+2</math> to each of these cases respectively gives us our final result.
	</div></div>		</div></div>
			In effect, the halting problem for the 5-state busy beaver winner is about whether repeatedly applying the function <math display="inline">f(n)=3n+6-4\left\lfloor\frac{n}{3}\right\rfloor</math> eventually produces a value of <math>n</math> that is congruent to 2 modulo 3.
	== Trajectory ==		== Trajectory ==
	The initial blank tape represents <math>g(0)</math>, and the [[Collatz-like]] rules are iterated 15 times before halting:		The initial blank tape represents <math>g(0)</math>, and the [[Collatz-like]] rules are iterated 15 times before halting:
Line 38:		Line 58:
	g(114)&\xrightarrow{7957}&g(196)&\xrightarrow{22777}&g(334)&\xrightarrow{64407}&g(564)&\xrightarrow{180307}&g(946)&\xrightarrow{504027}\\		g(114)&\xrightarrow{7957}&g(196)&\xrightarrow{22777}&g(334)&\xrightarrow{64407}&g(564)&\xrightarrow{180307}&g(946)&\xrightarrow{504027}\\
	g(1584)&\xrightarrow{1403967}&g(2646)&\xrightarrow{3906393}&g(4416)&\xrightarrow{10861903}&g(7366)&\xrightarrow{30196527}&g(12284)&\xrightarrow{24576}\end{array}\\0^\infty\;1\;\textrm{Z>}\;01\;001^{4095}\;1\;0^\infty\\\hline\end{array}</math>		g(1584)&\xrightarrow{1403967}&g(2646)&\xrightarrow{3906393}&g(4416)&\xrightarrow{10861903}&g(7366)&\xrightarrow{30196527}&g(12284)&\xrightarrow{24576}\end{array}\\0^\infty\;1\;\textrm{Z>}\;01\;001^{4095}\;1\;0^\infty\\\hline\end{array}</math>
	~~''To view an animation of <math>g(0)</math> becoming <math>g(34)</math> in 365 steps, click [https://wiki.bbchallenge.org/w/images/f/f1/BB5Champ_0-365.gif here].''~~
	== References ==		== References ==

MrSolis at 04:20, 5 March 2025

2025-03-05T04:20:47Z

← Older revision		Revision as of 04:20, 5 March 2025
Line 26:		Line 26:
	<math display="block">\begin{array}{\|c\|}\hline C(m,n)\xrightarrow{2m+8}C(m+5,n-1)\text{ if }n\ge 1.\\\hline\end{array}</math>		<math display="block">\begin{array}{\|c\|}\hline C(m,n)\xrightarrow{2m+8}C(m+5,n-1)\text{ if }n\ge 1.\\\hline\end{array}</math>
	We have <math>g(x)=C(x-1,0)</math>. As a result, if <math>x\equiv0\ (\operatorname{mod}3)</math>, we then get <math display="inline">C\Big(0,\frac{1}{3}x+1\Big)</math> and the above rule is applied until we reach <math display="inline">C\Big(\frac{5}{3}x+5,0\Big)</math>, equal to <math display="inline">g\Big(\frac{5}{3}x+6\Big)</math>, in <math>\sum_{i=0}^{x/3}(2\times 5i+8)=\textstyle\frac{5}{9}x^2+\frac{13}{3}x+8</math> steps for a total of <math display="inline">\frac{5}{9}x^2+\frac{19}{3}x+15</math> steps from <math>g(x)</math> (with <math>g(0)</math> we see the impossible configuration <math>C(-1,0)</math>, but it reaches <math>g(6)</math> in 15 steps regardless). However, if <math>x\equiv1\ (\operatorname{mod}3)</math>, we then get <math display="inline">C\Big(3,\frac{x+2}{3}\Big)</math> which reaches <math display="inline">C\Big(3+\frac{5(x+2)}{3},0\Big)</math>, equal to <math display="inline">g\Big(\frac{5x+22}{3}\Big)</math>, in <math display="inline">\frac{5}{9}x^2+\frac{47}{9}x+\frac{74}{9}</math> steps (<math display="inline">\frac{5}{9}x^2+\frac{65}{9}x+\frac{173}{9}</math> steps total).		We have <math>g(x)=C(x-1,0)</math>. As a result, if <math>x\equiv0\ (\operatorname{mod}3)</math>, we then get <math display="inline">C\Big(0,\frac{1}{3}x+1\Big)</math> and the above rule is applied until we reach <math display="inline">C\Big(\frac{5}{3}x+5,0\Big)</math>, equal to <math display="inline">g\Big(\frac{5}{3}x+6\Big)</math>, in <math>\sum_{i=0}^{x/3}(2\times 5i+8)=\textstyle\frac{5}{9}x^2+\frac{13}{3}x+8</math> steps for a total of <math display="inline">\frac{5}{9}x^2+\frac{19}{3}x+15</math> steps from <math>g(x)</math> (with <math>g(0)</math> we see the impossible configuration <math>C(-1,0)</math>, but it reaches <math>g(6)</math> in 15 steps regardless). However, if <math>x\equiv1\ (\operatorname{mod}3)</math>, we then get <math display="inline">C\Big(3,\frac{x+2}{3}\Big)</math> which reaches <math display="inline">C\Big(3+\frac{5(x+2)}{3},0\Big)</math>, equal to <math display="inline">g\Big(\frac{5x+22}{3}\Big)</math>, in <math display="inline">\frac{5}{9}x^2+\frac{47}{9}x+\frac{74}{9}</math> steps (<math display="inline">\frac{5}{9}x^2+\frac{65}{9}x+\frac{173}{9}</math> steps total).


	The information above can be summarized as<ref>Aaronson, S. (2020). The Busy Beaver Frontier. Page 10-11. https://www.scottaaronson.com/papers/bb.pdf</ref>		The information above can be summarized as<ref>Aaronson, S. (2020). The Busy Beaver Frontier. Page 10-11. https://www.scottaaronson.com/papers/bb.pdf</ref>
Line 32:		Line 31:
	Substituting <math>x\leftarrow 3x</math>, <math>x\leftarrow 3x+1</math>, and <math>x\leftarrow 3x+2</math> to each of these cases respectively gives us our final result.		Substituting <math>x\leftarrow 3x</math>, <math>x\leftarrow 3x+1</math>, and <math>x\leftarrow 3x+2</math> to each of these cases respectively gives us our final result.
	</div></div>		</div></div>

	== Trajectory ==		== Trajectory ==
	The initial blank tape represents <math>g(0)</math>, and the [[Collatz-like]] rules are iterated 15 times before halting:		The initial blank tape represents <math>g(0)</math>, and the [[Collatz-like]] rules are iterated 15 times before halting:

MrSolis at 15:37, 2 March 2025

2025-03-02T15:37:55Z

← Older revision		Revision as of 15:37, 2 March 2025
Line 3:		Line 3:
	[[File:5-state_Busy_Beaver_TransitionTable.png\|right\|100px\|thumb\|The transition table of the 5-state busy beaver winner.]]		[[File:5-state_Busy_Beaver_TransitionTable.png\|right\|100px\|thumb\|The transition table of the 5-state busy beaver winner.]]
	The 5-state busy beaver winner essentially maintains an integer variable <math>x</math> starting at 0, which is represented on the tape as <math>x</math> consecutive <math>1</math>s. After some steps, the head will instead find itself to the left of a series of <math>001</math>s on the tape. If <math>x</math> was congruent to 2 modulo 3 then this machine will halt; otherwise, the head will move back and forth many times, replacing one-by-one every "block" of <math>001</math> with <math>1</math>s. Because each back-and-forth movement makes the head visit two new cells on the left, turning them into <math>1</math>s, the new value for <math>x</math> is approximately <math display="inline">\frac{5}{3}x</math>. The space-time diagram of this machine appears similar to that of a [[Bell]].		The 5-state busy beaver winner essentially maintains an integer variable <math>x</math> starting at 0, which is represented on the tape as <math>x</math> consecutive <math>1</math>s. After some steps, the head will instead find itself to the left of a series of <math>001</math>s on the tape. If <math>x</math> was congruent to 2 modulo 3 then this machine will halt; otherwise, the head will move back and forth many times, replacing one-by-one every "block" of <math>001</math> with <math>1</math>s. Because each back-and-forth movement makes the head visit two new cells on the left, turning them into <math>1</math>s, the new value for <math>x</math> is approximately <math display="inline">\frac{5}{3}x</math>. The space-time diagram of this machine appears similar to that of a [[Bell]].
	==Attributions==		=== Attributions ===
	The 5-state busy beaver winner and its step count were first reported on by Heiner Marxen and Jürgen Buntrock in February 1990.<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref> The high-level rules were first demonstrated by Michael Buro in November 1990.<ref>Buro, Michael (November 1990). "Ein Beitrag zur Bestimmung von Rados <math>\Sigma(5)</math> oder Wie fängt man fleißige Biber?" [A contribution to the determination of Rado's <math>\Sigma(5)</math> - or - How to catch busy beavers?]. ''Schriften zur Informatik und angewandten Mathematik'' (Report No. 146). Rheinisch-Westfälische Technische Hochschule Aachen. https://skatgame.net/mburo/ps/diploma.pdf</ref>		The 5-state busy beaver winner and its step count were first reported on by Heiner Marxen and Jürgen Buntrock in February 1990.<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref> The high-level rules were first demonstrated by Michael Buro in November 1990.<ref>Buro, Michael (November 1990). "Ein Beitrag zur Bestimmung von Rados <math>\Sigma(5)</math> oder Wie fängt man fleißige Biber?" [A contribution to the determination of Rado's <math>\Sigma(5)</math> - or - How to catch busy beavers?]. ''Schriften zur Informatik und angewandten Mathematik'' (Report No. 146). Rheinisch-Westfälische Technische Hochschule Aachen. https://skatgame.net/mburo/ps/diploma.pdf</ref>
	== Analysis ==		== Analysis ==

← Older revision		Revision as of 21:55, 7 October 2025
Line 27:		Line 27:
	The transition table of the 5-state busy beaver winner.</div>		The transition table of the 5-state busy beaver winner.</div>
	== Analysis ==		== Analysis ==
	Let <math>g(x):=0^\infty\;<\~~text~~{A}\,1^x\;0^\infty</math>. Then,<ref>Pascal Michel. Behavior of busy beavers. https://bbchallenge.org/~pascal.michel/beh#tm52a</ref>		Let <math>g(x):=0^\infty\;\textrm{<}\textrm{A}\,1^x\;0^\infty</math>. Then,<ref>Pascal Michel. Behavior of busy beavers. https://bbchallenge.org/~pascal.michel/beh#tm52a</ref>
	<math display="block">\begin{array}{\|lll\|}\hline		<math display="block">\begin{array}{\|lll\|}\hline
	g(3x)&\xrightarrow{5x^2+19x+15}&g(5x+6),\\		g(3x)&\xrightarrow{5x^2+19x+15}&g(5x+6),\\
	g(3x+1)&\xrightarrow{5x^2+25x+27}&g(5x+9),\\		g(3x+1)&\xrightarrow{5x^2+25x+27}&g(5x+9),\\
	g(3x+2)&\xrightarrow{6x+12}&0^\infty\;1\;\~~text~~{Z}>\;01\;001^{x+1}\;1\;0^\infty.\\\hline		g(3x+2)&\xrightarrow{6x+12}&0^\infty\;1\;\textrm{Z}\textrm{>}\;01\;001^{x+1}\;1\;0^\infty.\\\hline
	\end{array}</math>		\end{array}</math>
	<div class="toccolours mw-collapsible mw-collapsed">'''Proof'''<div class="mw-collapsible-content">		<div class="toccolours mw-collapsible mw-collapsed">'''Proof'''<div class="mw-collapsible-content">
	Consider the configuration <math>C(m,n):=0^\infty\;\textrm{<A}\;1^m\;001^n\;1\;0^\infty</math>. After one step this configuration becomes <math>0^\infty\;1\;\textrm{B>}\;1^m\;001^n\;1\;0^\infty</math>. We note the following shift rule:		Consider the configuration <math>C(m,n):=0^\infty\;\textrm{<}\textrm{A}\;1^m\;001^n\;1\;0^\infty</math>. After one step this configuration becomes <math>0^\infty\;1\;\textrm{B}\textrm{>}\;1^m\;001^n\;1\;0^\infty</math>. We note the following shift rule:
	<math display="block">\begin{array}{\|c\|}\hline\textrm{B>}\;1^a\xrightarrow{a}1^a\;\textrm{B>}\\\hline\end{array}</math>		<math display="block">\begin{array}{\|c\|}\hline\textrm{B}\textrm{>}\;1^a\xrightarrow{a}1^a\;\textrm{B}\textrm{>}\\\hline\end{array}</math>
	Using this shift rule, we get <math>0^\infty\;1^{m+1}\;\textrm{B>}\;001^n\;1\;0^\infty</math> after <math>m</math> steps. If <math>n=0</math>, then we get <math>0^\infty\;1^{m+4}\;\textrm{<A}\;1\;0^\infty</math> four steps later. Another shift rule is needed here:		Using this shift rule, we get <math>0^\infty\;1^{m+1}\;\textrm{B}\textrm{>}\;001^n\;1\;0^\infty</math> after <math>m</math> steps. If <math>n=0</math>, then we get <math>0^\infty\;1^{m+4}\;\textrm{<}\textrm{A}\;1\;0^\infty</math> four steps later. Another shift rule is needed here:
	<math display="block">\begin{array}{\|c\|}\hline1^{3a}\;\textrm{<A}\xrightarrow{3a}\textrm{<A}\;001^a\\\hline\end{array}</math>		<math display="block">\begin{array}{\|c\|}\hline1^{3a}\;\textrm{<}\textrm{A}\xrightarrow{3a}\textrm{<}\textrm{A}\;001^a\\\hline\end{array}</math>
	In this instance, <math display="inline">\Big\lfloor\frac{m+4}{3}\Big\rfloor</math> is substituted for <math>a</math>, which creates three different scenarios depending on the value of <math>m</math> modulo 3. They are as follows:		In this instance, <math display="inline">\Big\lfloor\frac{m+4}{3}\Big\rfloor</math> is substituted for <math>a</math>, which creates three different scenarios depending on the value of <math>m</math> modulo 3. They are as follows:
	# If <math>m+4\equiv0\ (\operatorname{mod}3)</math>, then in <math>m+4</math> steps we arrive at <math>0^\infty\;\textrm{<A}\;001^{(m+4)/3}\;1\;0^\infty</math>, which is the same configuration as <math display="inline">C\Big(0,\frac{m+4}{3}\Big)</math>.		# If <math>m+4\equiv0\ (\operatorname{mod}3)</math>, then in <math>m+4</math> steps we arrive at <math>0^\infty\;\textrm{<}\textrm{A}\;001^{(m+4)/3}\;1\;0^\infty</math>, which is the same configuration as <math display="inline">C\Big(0,\frac{m+4}{3}\Big)</math>.
	# If <math>m+4\equiv1\ (\operatorname{mod}3)</math>, then in <math>m+3</math> steps we arrive at <math>0^\infty\;1\;\textrm{<A}\;001^{(m+3)/3}\;1\;0^\infty</math>, which in five steps becomes <math>0^\infty\;\textrm{<A}\;111\;001^{(m+3)/3}\;1\;0^\infty</math>, equal to <math display="inline">C\Big(3,\frac{m+3}{3}\Big)</math>.		# If <math>m+4\equiv1\ (\operatorname{mod}3)</math>, then in <math>m+3</math> steps we arrive at <math>0^\infty\;1\;\textrm{<}\textrm{A}\;001^{(m+3)/3}\;1\;0^\infty</math>, which in five steps becomes <math>0^\infty\;\textrm{<}\textrm{A}\;111\;001^{(m+3)/3}\;1\;0^\infty</math>, equal to <math display="inline">C\Big(3,\frac{m+3}{3}\Big)</math>.
	# If <math>m+4\equiv2\ (\operatorname{mod}3)</math>, then in <math>m+2</math> steps we arrive at <math>0^\infty\;11\;\textrm{<A}\;001^{(m+2)/3}\;1\;0^\infty</math>, which in three steps halts with the configuration <math>0^\infty\;1\;\textrm{Z>}\;01\;001^{(m+2)/3}\;1\;0^\infty</math>, for a total of <math>2m+10</math> steps from <math>C(m,0)</math>.		# If <math>m+4\equiv2\ (\operatorname{mod}3)</math>, then in <math>m+2</math> steps we arrive at <math>0^\infty\;11\;\textrm{<}\textrm{A}\;001^{(m+2)/3}\;1\;0^\infty</math>, which in three steps halts with the configuration <math>0^\infty\;1\;\textrm{Z}\textrm{>}\;01\;001^{(m+2)/3}\;1\;0^\infty</math>, for a total of <math>2m+10</math> steps from <math>C(m,0)</math>.
	Returning to <math>0^\infty\;1^{m+1}\;\textrm{B>}\;001^n\;1\;0^\infty</math>, if <math>n\ge 1</math>, then in three steps it changes into <math>0^\infty\;1^{m+3}\;\textrm{<D}\;1\;001^{n-1}\;1\;0^\infty</math>. Here we can make use of one more shift rule:		Returning to <math>0^\infty\;1^{m+1}\;\textrm{B}\textrm{>}\;001^n\;1\;0^\infty</math>, if <math>n\ge 1</math>, then in three steps it changes into <math>0^\infty\;1^{m+3}\;\textrm{<}\textrm{D}\;1\;001^{n-1}\;1\;0^\infty</math>. Here we can make use of one more shift rule:
	<math display="block">\begin{array}{\|c\|}\hline1^a\;\textrm{<D}\xrightarrow{a}\textrm{<D}\;1^a\\\hline\end{array}</math>		<math display="block">\begin{array}{\|c\|}\hline1^a\;\textrm{<}\textrm{D}\xrightarrow{a}\textrm{<}\textrm{D}\;1^a\\\hline\end{array}</math>
	Doing so takes us to <math>0^\infty\;\textrm{<D}\;1^{m+4}\;001^{n-1}\;1\;0^\infty</math> in <math>m+3</math> steps, which after one step becomes the configuration <math>0^\infty\;\textrm{<A}\;1^{m+5}\;001^{n-1}\;1\;0^\infty</math>, equal to <math>C(m+5,n-1)</math>. To summarize:		Doing so takes us to <math>0^\infty\;\textrm{<}\textrm{D}\;1^{m+4}\;001^{n-1}\;1\;0^\infty</math> in <math>m+3</math> steps, which after one step becomes the configuration <math>0^\infty\;\textrm{<}\textrm{A}\;1^{m+5}\;001^{n-1}\;1\;0^\infty</math>, equal to <math>C(m+5,n-1)</math>. To summarize:
	<math display="block">\begin{array}{\|c\|}\hline C(m,n)\xrightarrow{2m+8}C(m+5,n-1)\text{ if }n\ge 1.\\\hline\end{array}</math>		<math display="block">\begin{array}{\|c\|}\hline C(m,n)\xrightarrow{2m+8}C(m+5,n-1)\text{ if }n\ge 1.\\\hline\end{array}</math>
	We have <math>g(x)=C(x-1,0)</math>. As a result, if <math>x\equiv0\ (\operatorname{mod}3)</math>, we then get <math display="inline">C\Big(0,\frac{1}{3}x+1\Big)</math> and the above rule is applied until we reach <math display="inline">C\Big(\frac{5}{3}x+5,0\Big)</math>, equal to <math display="inline">g\Big(\frac{5}{3}x+6\Big)</math>, in <math>\sum_{i=0}^{x/3}(2\times 5i+8)=\textstyle\frac{5}{9}x^2+\frac{13}{3}x+8</math> steps for a total of <math display="inline">\frac{5}{9}x^2+\frac{19}{3}x+15</math> steps from <math>g(x)</math> (with <math>g(0)</math> we see the impossible configuration <math>C(-1,0)</math>, but it reaches <math>g(6)</math> in 15 steps regardless). However, if <math>x\equiv1\ (\operatorname{mod}3)</math>, we then get <math display="inline">C\Big(3,\frac{x+2}{3}\Big)</math> which reaches <math display="inline">C\Big(3+\frac{5(x+2)}{3},0\Big)</math>, equal to <math display="inline">g\Big(\frac{5x+22}{3}\Big)</math>, in <math display="inline">\frac{5}{9}x^2+\frac{47}{9}x+\frac{74}{9}</math> steps (<math display="inline">\frac{5}{9}x^2+\frac{65}{9}x+\frac{173}{9}</math> steps total).		We have <math>g(x)=C(x-1,0)</math>. As a result, if <math>x\equiv0\ (\operatorname{mod}3)</math>, we then get <math display="inline">C\Big(0,\frac{1}{3}x+1\Big)</math> and the above rule is applied until we reach <math display="inline">C\Big(\frac{5}{3}x+5,0\Big)</math>, equal to <math display="inline">g\Big(\frac{5}{3}x+6\Big)</math>, in <math>\sum_{i=0}^{x/3}(2\times 5i+8)=\textstyle\frac{5}{9}x^2+\frac{13}{3}x+8</math> steps for a total of <math display="inline">\frac{5}{9}x^2+\frac{19}{3}x+15</math> steps from <math>g(x)</math> (with <math>g(0)</math> we see the impossible configuration <math>C(-1,0)</math>, but it reaches <math>g(6)</math> in 15 steps regardless). However, if <math>x\equiv1\ (\operatorname{mod}3)</math>, we then get <math display="inline">C\Big(3,\frac{x+2}{3}\Big)</math> which reaches <math display="inline">C\Big(3+\frac{5(x+2)}{3},0\Big)</math>, equal to <math display="inline">g\Big(\frac{5x+22}{3}\Big)</math>, in <math display="inline">\frac{5}{9}x^2+\frac{47}{9}x+\frac{74}{9}</math> steps (<math display="inline">\frac{5}{9}x^2+\frac{65}{9}x+\frac{173}{9}</math> steps total).

	The information above can be summarized as<ref>Aaronson, S. (2020). The Busy Beaver Frontier. Page 10-11. https://www.scottaaronson.com/papers/bb.pdf</ref>		The information above can be summarized as<ref>Aaronson, S. (2020). The Busy Beaver Frontier. Page 10-11. https://www.scottaaronson.com/papers/bb.pdf</ref>
	<math display="block">g(x)\rightarrow\begin{cases}g\Big(\frac{5}{3}x+6\Big)&\text{if }x\equiv0\pmod{3},\\g\Big(\frac{5x+22}{3}\Big)&\text{if }x\equiv1\pmod{3},\\0^\infty\;1\;\textrm{Z>}\;01\;001^{(x+1)/3}\;1\;0^\infty&\text{if }x\equiv2\pmod{3}.\end{cases}</math>		<math display="block">g(x)\rightarrow\begin{cases}g\Big(\frac{5}{3}x+6\Big)&\text{if }x\equiv0\pmod{3},\\g\Big(\frac{5x+22}{3}\Big)&\text{if }x\equiv1\pmod{3},\\0^\infty\;1\;\textrm{Z}\textrm{>}\;01\;001^{(x+1)/3}\;1\;0^\infty&\text{if }x\equiv2\pmod{3}.\end{cases}</math>
	Substituting <math>x\leftarrow 3x</math>, <math>x\leftarrow 3x+1</math>, and <math>x\leftarrow 3x+2</math> to each of these cases respectively gives us our final result.		Substituting <math>x\leftarrow 3x</math>, <math>x\leftarrow 3x+1</math>, and <math>x\leftarrow 3x+2</math> to each of these cases respectively gives us our final result.
	</div></div>		</div></div>
Line 58:		Line 58:
	g(0)&\xrightarrow{15}&g(6)&\xrightarrow{73} &g(16)&\xrightarrow{277}&g(34)&\xrightarrow{907}&g(64)&\xrightarrow{2757}\\		g(0)&\xrightarrow{15}&g(6)&\xrightarrow{73} &g(16)&\xrightarrow{277}&g(34)&\xrightarrow{907}&g(64)&\xrightarrow{2757}\\
	g(114)&\xrightarrow{7957}&g(196)&\xrightarrow{22777}&g(334)&\xrightarrow{64407}&g(564)&\xrightarrow{180307}&g(946)&\xrightarrow{504027}\\		g(114)&\xrightarrow{7957}&g(196)&\xrightarrow{22777}&g(334)&\xrightarrow{64407}&g(564)&\xrightarrow{180307}&g(946)&\xrightarrow{504027}\\
	g(1584)&\xrightarrow{1403967}&g(2646)&\xrightarrow{3906393}&g(4416)&\xrightarrow{10861903}&g(7366)&\xrightarrow{30196527}&g(12284)&\xrightarrow{24576}\end{array}\\0^\infty\;1\;\~~text~~{Z}>\;01\;001^{4095}\;1\;0^\infty\\\hline\end{array}</math>		g(1584)&\xrightarrow{1403967}&g(2646)&\xrightarrow{3906393}&g(4416)&\xrightarrow{10861903}&g(7366)&\xrightarrow{30196527}&g(12284)&\xrightarrow{24576}\end{array}\\0^\infty\;1\;\textrm{Z}\textrm{>}\;01\;001^{4095}\;1\;0^\infty\\\hline\end{array}</math>
	== References ==		== References ==
	<references/>		<references/>
	[[Category:BB(5)]]		[[Category:BB(5)]]