Revision as of 22:43, 1 February 2025

5-state busy beaver winner (WIP Revamp)

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 $BB (5) \geq 47176870$ and $Σ (5) \geq 4098$ at the time.

Analysis

Rules

Let $g (x) : = 0^{\infty} < A 1^{x} 0^{\infty}$ . Then^[2], $\begin{array}{lll} g (3 x) & \overset{5 x^{2} + 19 x + 15}{\to} & g (5 x + 6), \\ g (3 x + 1) & \overset{5 x^{2} + 25 x + 27}{\to} & g (5 x + 9), \\ g (3 x + 2) & \overset{6 x + 12}{\to} & 0^{\infty} 1 Z > 01 00 1^{x + 1} 1 0^{\infty} . \end{array}$

Proof

Consider the configuration $C (m, n) : = 0^{\infty} < A 1^{m} 00 1^{n} 1 0^{\infty}$ . After one step this configuration becomes $0^{\infty} 1 B > 1^{m} 00 1^{n} 1 0^{\infty}$ . We note the following shift rule: $\begin{array}{c} B > 1^{a} \overset{a}{\to} 1^{a} B > \end{array}$ Using this shift rule, we get $0^{\infty} 1^{m + 1} B > 00 1^{n} 1 0^{\infty}$ after $m$ steps. If $n = 0$ , then we get $0^{\infty} 1^{m + 4} < A 1 0^{\infty}$ four steps later. Another shift rule is needed here: $1^{3 a} < A \overset{3 a}{\to} < A 00 1^{a}$ In this instance, $⌊ \frac{m + 4}{3} ⌋$ is substituted for $a$ , which creates three different scenarios depending on the value of $m$ modulo 3. They are as follows:

If $m + 4 \equiv 0 (\mod 3)$ , then in $m + 4$ steps we arrive at $0^{\infty} < A 00 1^{(m + 4) / 3} 1 0^{\infty}$ , which is the same configuration as $C (0, \frac{m + 4}{3})$ .
If $m + 4 \equiv 1 (\mod 3)$ , then in $m + 3$ steps we arrive at $0^{\infty} 1 < A 00 1^{(m + 3) / 3} 1 0^{\infty}$ , which is five steps becomes $0^{\infty} < A 111 00 1^{(m + 3) / 3} 1 0^{\infty}$ , or $C (3, \frac{m + 3}{3})$ .
If $m + 4 \equiv 2 (\mod 3)$ , then in $m + 2$ steps we arrive at $0^{\infty} 11 < A 00 1^{(m + 2) / 3} 1 0^{\infty}$ , which in three steps halts with the configuration $0^{\infty} 1 Z > 01 00 1^{(m + 2) / 3} 1 0^{\infty}$ , for a total of $2 m + 10$ steps from $C (m, n)$ .

Returning to $0^{\infty} 1^{m + 1} B > 00 1^{n} 1 0^{\infty}$ , if $n \geq 1$ , then in three steps it changes into $0^{\infty} 1^{m + 3} < D 1 00 1^{n - 1} 1 0^{\infty}$ . Here we can make use of one more shift rule: $1^{a} < D \overset{a}{\to} < D 1^{a}$ Doing so takes us to $0^{\infty} < D 1^{m + 4} 00 1^{n - 1} 1 0^{\infty}$ in $m + 3$ steps, which after one step becomes the configuration $0^{\infty} < A 1^{m + 5} 00 1^{n - 1} 1 0^{\infty}$ , or $C (m + 5, n - 1)$ . To summarize: $C (m, n) \overset{2 m + 8}{\to} C (m + 5, n - 1) if n \geq 1 .$ We have $g (x) = C (x - 1, 0)$ . As a result, if $x \equiv 0 (\mod 3)$ , we then get $C (0, \frac{1}{3} x + 1)$ and the above rule is applied until we reach $C (\frac{5}{3} x + 5, 0)$ , equivalent to $g (\frac{5}{3} x + 6)$ , in $\sum_{i = 0}^{x / 3} (2 \times 5 i + 8) = \frac{5}{9} x^{2} + \frac{13}{3} x + 8$ steps for a total of $\frac{5}{9} x^{2} + \frac{19}{3} + 15$ steps from $g (x)$ (with $g (0)$ we see the impossible configuration $C (- 1, 0)$ , but it reaches $g (6)$ in 15 steps regardless). However, if $x \equiv 1 (\mod 3)$ , we then get $C (3, \frac{x + 2}{3})$ which reaches $C (3 + \frac{5 (x + 2)}{3})$ , or $g (\frac{5 x + 22}{3})$ , in $\frac{5}{9} x^{2} + \frac{47}{9} x + \frac{74}{9}$ steps ( $\frac{5}{9} x^{2} + \frac{65}{9} x + \frac{173}{9}$ steps total).

The information above can be summarized as^[3] $g (x) \to {\begin{cases} g (\frac{5}{3} x + 6) & if x \equiv 0 (\mod 3) \\ g (\frac{5 x + 22}{3}) & if x \equiv 1 (\mod 3) \\ 0^{\infty} 1 Z > 01 00 1^{(x + 1) / 3} 1 0^{\infty} & if x \equiv 2 (\mod 3) \end{cases}$ Substituting $x \leftarrow 3 x$ , $x \leftarrow 3 x + 1$ , and $x \leftarrow 3 x + 2$ to each of these cases respectively gives us our final result.

Trajectory

The initial blank tape represents $g (0)$ , and the rules are iterated 15 times before halting: $\begin{array}{lllllllllll} g (0) & \overset{15}{\to} & g (6) & \overset{73}{\to} & g (16) & \overset{277}{\to} \\ g (34) & \overset{907}{\to} & g (64) & \overset{2757}{\to} & g (114) & \overset{7957}{\to} \\ g (196) & \overset{22777}{\to} & g (334) & \overset{64407}{\to} & g (564) & \overset{180307}{\to} \\ g (946) & \overset{504027}{\to} & g (1584) & \overset{1403967}{\to} & g (2646) & \overset{3906393}{\to} \\ g (4416) & \overset{10861903}{\to} & g (7366) & \overset{30196527}{\to} & g (12284) & \overset{24576}{\to} & 0^{\infty} 1 Z > 01 00 1^{4095} 1 0^{\infty} \end{array}$

References

↑ 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
↑ Pascal Michel. Behavior of busy beavers.https://bbchallenge.org/~pascal.michel/beh#tm52a
↑ Aaronson, S. (2020). The Busy Beaver Frontier. Page 10-11. https://www.scottaaronson.com/papers/bb.pdf

[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] Pascal Michel. Behavior of busy beavers.https://bbchallenge.org/~pascal.michel/beh#tm52a

[3] Aaronson, S. (2020). The Busy Beaver Frontier. Page 10-11. https://www.scottaaronson.com/papers/bb.pdf

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
-=5-state busy beaver winner (Remake)=
+=5-state busy beaver winner (WIP Revamp)=
 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.
 == Analysis ==
 ===Rules===
-Let <math>g(x):=0^\infty\;\textrm{<A}\,1^x\;0^\infty</math>. Then,
+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>,
-<math display="block">\begin{array}{lll}
+<math display="block">\begin{array}{lll}\\
 g(3x)&\phantom{}\xrightarrow{5x^2+19x+15}&g(5x+6),\\
 g(3x+1)&\phantom{}\xrightarrow{5x^2+25x+27}&g(5x+9),\\
-g(3x+2)\phantom{}&\xrightarrow{6x+12}&0^\infty\;1\;\textrm{Z>}\;01\;001^{x+1}\;1\;0^\infty
+g(3x+2)\phantom{}&\xrightarrow{6x+12}&0^\infty\;1\;\textrm{Z>}\;01\;001^{x+1}\;1\;0^\infty.
 \end{array}</math>
 ===Proof===
-WIP
+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:
+<math display="block">\begin{array}{c}\\\textrm{B>}\;1^a\xrightarrow{a}1^a\;\textrm{B>}\phantom{}\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">1^{3a}\;\textrm{<A}\xrightarrow{3a}\textrm{<A}\;001^a</math>
+In this instance, <math>\lfloor\frac{m+4}{3}\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\equiv 0\pmod{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>C(0,\frac{m+4}{3})</math>.
+# If <math>m+4\equiv 1\pmod{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>, or <math>C(3,\frac{m+3}{3})</math>.
+# If <math>m+4\equiv 2\pmod{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,n)</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">1^a\;\textrm{<D}\xrightarrow{a}\textrm{<D}\;1^a</math>
+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>, or <math>C(m+5,n-1)</math>. To summarize:
+<math display="block">C(m,n)\xrightarrow{2m+8}C(m+5,n-1)\text{ if }n\ge 1.</math>
+We have <math>g(x)=C(x-1,0)</math>. As a result, if <math>x\equiv 0\pmod{3}</math>, we then get <math>C(0,\frac{1}{3}x+1)</math> and the above rule is applied until we reach <math>C(\frac{5}{3}x+5,0)</math>, equivalent to <math>g(\frac{5}{3}x+6)</math>, in <math>\sum_{i=0}^{x/3}(2\times 5i+8)=\frac{5}{9}x^2+\frac{13}{3}x+8\phantom{}</math> steps for a total of <math>\frac{5}{9}x^2+\frac{19}{3}+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\equiv 1\pmod{3}</math>, we then get <math>C(3,\frac{x+2}{3})</math> which reaches <math>C(3+\frac{5(x+2)}{3})</math>, or <math>g(\frac{5x+22}{3})</math>, in <math>\frac{5}{9}x^2+\frac{47}{9}x+\frac{74}{9}</math> steps (<math>\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 rules are iterated 15 times before halting:
+<math display="block">\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} &0^\infty\;1\;\textrm{Z>}\;01\;001^{4095}\;1\;0^\infty\end{array}</math>
+== References ==

User:MrSolis/Playground: Difference between revisions

Revision as of 22:43, 1 February 2025

Contents

5-state busy beaver winner (WIP Revamp)

Analysis

Rules

Proof

Trajectory

References

Navigation menu

User:MrSolis/Playground: Difference between revisions

Revision as of 22:43, 1 February 2025

5-state busy beaver winner (WIP Revamp)

Analysis

Rules

Proof

Trajectory

References

Navigation menu

Search