Revision as of 22:53, 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, 0)$ .

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}, 0)$ , 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 17: / Line 17: @@
 # 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>.
+# 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,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">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).
+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},0)\phantom{}</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>

User:MrSolis/Playground: Difference between revisions

Revision as of 22:53, 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:53, 1 February 2025

5-state busy beaver winner (WIP Revamp)

Analysis

Rules

Proof

Trajectory

References

Navigation menu

Search