The 5-state busy beaver ([[BB(5)]]) winner is {{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}. Discovered by Heiner Marxen and Jürgen Buntrock in 1989<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>, this machine proved that <math>\operatorname{BB}(5)\ge 47176870\phantom{}</math> and <math>\Sigma(5)\ge 4098</math> at the time.
The 5-state busy beaver ([[BB(5)]]) winner is {{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}. Discovered by Heiner Marxen and Jürgen Buntrock in 1989<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>, this machine proved that <math>\operatorname{BB}(5)\ge 47176870</math> and <math>\Sigma(5)\ge 4098</math> at the time.
== Analysis ==
== Analysis ==
===Rules===
===Rules===
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>,
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\phantom{}</math>. We note the following shift rule:
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:
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>}\;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:
Line 16:
Line 16:
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{<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 is five steps becomes <math>\phantom{}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{<A}\;001^{(m+3)/3}\;1\;0^\infty</math>, which is 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\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{<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>.
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>}\;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:
Doing so takes us to <math>0^\infty\;\textrm{<D}\;1^{m+4}\;001^{n-1}\;1\;\phantom{}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{<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:
<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>
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.
== Trajectory ==
== Trajectory ==
[[File:BB5Champ 0-365.gif|right|thumb|An animation of <math>g(0)</math> becoming <math>g(34)</math> in 365 steps (''click to view'').]]
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:
The 5-state busy beaver (BB(5)) winner is 1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA (bbch). Discovered by Heiner Marxen and Jürgen Buntrock in 1989[1], this machine proved that and at the time.
Consider the configuration . After one step this configuration becomes . We note the following shift rule:
Using this shift rule, we get after steps. If , then we get four steps later. Another shift rule is needed here:
In this instance, is substituted for , which creates three different scenarios depending on the value of modulo 3. They are as follows:
If , then in steps we arrive at , which is the same configuration as .
If , then in steps we arrive at , which is five steps becomes , equal to .
If , then in steps we arrive at , which in three steps halts with the configuration , for a total of steps from .
Returning to , if , then in three steps it changes into . Here we can make use of one more shift rule:
Doing so takes us to in steps, which after one step becomes the configuration , equal to . To summarize:
We have . As a result, if , we then get and the above rule is applied until we reach , equal to , in steps for a total of steps from (with we see the impossible configuration , but it reaches in 15 steps regardless). However, if , we then get which reaches , equal to , in steps ( steps total).
The information above can be summarized as[3]
Substituting , , and to each of these cases respectively gives us our final result.
Trajectory
An animation of becoming in 365 steps (click to view).
The initial blank tape represents , and the Collatz-like rules are iterated 15 times before halting:
