5-state busy beaver winner: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
No edit summary
No edit summary
Tag: Manual revert
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)]]. This machine 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.
The 5-state busy beaver ([[BB(5)]]) champion (and winner!) is: {{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}. It was found 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>. The machine halts after 47,176,870 steps and with 4098 1's on the tape, showing that <math>BB(5) \ge 47{,}176{,}870</math> and <math>\Sigma(5) \ge 4098</math>.
== Analysis ==
 
===Rules===
== Behavior ==
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>,
This machine repeatedly applies the following [[Collatz-like]] map, starting with <math>x = 0</math><ref>Aaronson, S. (2020). The Busy Beaver Frontier. Page 10-11. https://www.scottaaronson.com/papers/bb.pdf</ref>:
<math display="block">\begin{array}{|lll|}\hline
<math display="block">\begin{align}
g(3x)&\xrightarrow{5x^2+19x+15}&g(5x+6),\\
  g(x) & \to \frac{5x+18}{3} && \text{if }x \equiv 0 \pmod{3} \\
g(3x+1)&\xrightarrow{5x^2+25x+27}&g(5x+9),\\
  g(x) & \to \frac{5x+22}{3} && \text{if }x \equiv 1 \pmod{3} \\
g(3x+2)&\xrightarrow{6x+12}&0^\infty\;1\;\textrm{Z>}\;01\;001^{x+1}\;1\;0^\infty.\\\hline
  g(x) & \to \text{HALT}    && \text{if }x \equiv 2 \pmod{3}
\end{align}</math>which can alternatively be written as<ref>Pascal Michel. Behavior of busy beavers.https://bbchallenge.org/~pascal.michel/beh#tm52a</ref>:
 
<math display="block">\begin{align}
  g(3k)   & \to 5k+6 \\
  g(3k+1) & \to 5k+9 \\
  g(3k+2) & \to \text{HALT} \\
\end{align}</math>
 
The full orbit from <math>x = 0</math> is:
<math display="block">\begin{array}{l}
  0    & \to & 6    & \to & 16  & \to & 34  & \to & 64    & \to & \\
  114  & \to & 196  & \to & 334  & \to & 564  & \to & 946  & \to & \\
  1584 & \to & 2646 & \to & 4416 & \to & 7366 & \to & 12284 & \to & \text{HALT}
\end{array}</math>
\end{array}</math>
===Proof===
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:
<math display="block">\begin{array}{|c|}\hline\textrm{B>}\;1^a\xrightarrow{a}1^a\;\textrm{B>}\\\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:
<math display="block">\begin{array}{|c|}\hline1^{3a}\;\textrm{<A}\xrightarrow{3a}\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:
# 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 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\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:
<math display="block">\begin{array}{|c|}\hline1^a\;\textrm{<D}\xrightarrow{a}\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:
<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).


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>
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 ==
The initial blank tape represents <math>g(0)</math>, and the [[Collatz-like]] rules are iterated 15 times before halting:
[[File:BB5Champ 0-365.gif|right|thumb|An animation of <math>g(0)</math> becoming <math>g(34)</math> in 365 steps (''[https://wiki.bbchallenge.org/w/images/f/f1/BB5Champ_0-365.gif click to view]'').]]
<math display="block">\begin{array}{|l|}\hline\begin{array}{lllllllllll}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(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 ==

Revision as of 17:39, 17 February 2025

The 5-state busy beaver (BB(5)) champion (and winner!) is: 1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA (bbch). It was found by Heiner Marxen and Jürgen Buntrock in 1989[1]. The machine halts after 47,176,870 steps and with 4098 1's on the tape, showing that and .

Behavior

This machine repeatedly applies the following Collatz-like map, starting with [2]:

which can alternatively be written as[3]:

The full orbit from is:

References

  1. ↑ 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
  2. ↑ Aaronson, S. (2020). The Busy Beaver Frontier. Page 10-11. https://www.scottaaronson.com/papers/bb.pdf
  3. ↑ Pascal Michel. Behavior of busy beavers.https://bbchallenge.org/~pascal.michel/beh#tm52a
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=5-state_busy_beaver_winner&oldid=1575"