5-state busy beaver winner

The 5-state busy beaver winner is the Turing machine whose step count determines BB(5). Up to permutations, that machine is 1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA (bbch), which halts after 47176870 steps with 4098 ones on the tape.

Description

The transition table of this Turing machine.

This machine essentially maintains an integer variable $x$ that is represented as the head being to the left of $x$ consecutive $1$s on the tape, starting at 0. After some steps, the head will instead find itself to the left of a chain of $001$s on the tape. If $x$ was previously found to be congruent to 2 modulo 3 then this machine will halt. Otherwise, $x$ is updated by means of each "block" of $001$ being replaced by $1$s through a series of repetitive back and forth head movements. Each back and forth movement takes longer than the previous one and makes the head visit two new cells, turning them into $1$s. As a result, the space-time diagram of this machine appears similar to that of a Bell, and by the time all of the $001$s have been replaced by $1$s, $x$ will have roughly multiplied itself by ${\textstyle {\frac {5}{3}}}$. Until this machine halts, $x$ is repeatedly updated in the manner explained here.

Attributions

This machine and its step count were first reported on by Heiner Marxen and Jürgen Buntrock in February 1990. The high-level rules were first demonstrated by Michael Buro in November 1990.

Analysis

Let $g(x):=0^{\infty }\;{\textrm {<A}}\,1^{x}\;0^{\infty }$. Then,

$${\begin{array}{|lll|}\hline g(3x)&\xrightarrow {5x^{2}+19x+15} &g(5x+6),\\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 \end{array}}$$

Proof

Consider the configuration $C(m,n):=0^{\infty }\;{\textrm {<A}}\;1^{m}\;001^{n}\;1\;0^{\infty }$. After one step this configuration becomes $0^{\infty }\;1\;{\textrm {B>}}\;1^{m}\;001^{n}\;1\;0^{\infty }$. We note the following shift rule:

$${\begin{array}{|c|}\hline {\textrm {B>}}\;1^{a}\xrightarrow {a} 1^{a}\;{\textrm {B>}}\\\hline \end{array}}$$

Using this shift rule, we get $0^{\infty }\;1^{m+1}\;{\textrm {B>}}\;001^{n}\;1\;0^{\infty }$ after $m$ steps. If $n=0$, then we get $0^{\infty }\;1^{m+4}\;{\textrm {<A}}\;1\;0^{\infty }$ four steps later. Another shift rule is needed here:

$${\begin{array}{|c|}\hline 1^{3a}\;{\textrm {<A}}\xrightarrow {3a} {\textrm {<A}}\;001^{a}\\\hline \end{array}}$$

In this instance, ${\textstyle {\Big \lfloor }{\frac {m+4}{3}}{\Big \rfloor }}$ is substituted for $a$, which creates three different scenarios depending on the value of $m$ modulo 3. They are as follows:

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

Returning to $0^{\infty }\;1^{m+1}\;{\textrm {B>}}\;001^{n}\;1\;0^{\infty }$, if $n\geq 1$, then in three steps it changes into $0^{\infty }\;1^{m+3}\;{\textrm {<D}}\;1\;001^{n-1}\;1\;0^{\infty }$. Here we can make use of one more shift rule:

$${\begin{array}{|c|}\hline 1^{a}\;{\textrm {<D}}\xrightarrow {a} {\textrm {<D}}\;1^{a}\\\hline \end{array}}$$

Doing so takes us to $0^{\infty }\;{\textrm {<D}}\;1^{m+4}\;001^{n-1}\;1\;0^{\infty }$ in $m+3$ steps, which after one step becomes the configuration $0^{\infty }\;{\textrm {<A}}\;1^{m+5}\;001^{n-1}\;1\;0^{\infty }$, equal to $C(m+5,n-1)$. To summarize:

$${\begin{array}{|c|}\hline C(m,n)\xrightarrow {2m+8} C(m+5,n-1){\text{ if }}n\geq 1.\\\hline \end{array}}$$

We have $g(x)=C(x-1,0)$. As a result, if $x\equiv 0\ (\operatorname {mod} 3)$, we then get ${\textstyle C{\Big (}0,{\frac {1}{3}}x+1{\Big )}}$ and the above rule is applied until we reach ${\textstyle C{\Big (}{\frac {5}{3}}x+5,0{\Big )}}$, equal to ${\textstyle g{\Big (}{\frac {5}{3}}x+6{\Big )}}$, in $\sum _{i=0}^{x/3}(2\times 5i+8)=\textstyle {\frac {5}{9}}x^{2}+{\frac {13}{3}}x+8$ steps for a total of ${\textstyle {\frac {5}{9}}x^{2}+{\frac {19}{3}}x+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\ (\operatorname {mod} 3)$, we then get ${\textstyle C{\Big (}3,{\frac {x+2}{3}}{\Big )}}$ which reaches ${\textstyle C{\Big (}3+{\frac {5(x+2)}{3}},0{\Big )}}$, equal to ${\textstyle g{\Big (}{\frac {5x+22}{3}}{\Big )}}$, in ${\textstyle {\frac {5}{9}}x^{2}+{\frac {47}{9}}x+{\frac {74}{9}}}$ steps (${\textstyle {\frac {5}{9}}x^{2}+{\frac {65}{9}}x+{\frac {173}{9}}}$ steps total).

The information above can be summarized as

$$g(x)\rightarrow {\begin{cases}g{\Big (}{\frac {5}{3}}x+6{\Big )}&{\text{if }}x\equiv 0{\pmod {3}},\\g{\Big (}{\frac {5x+22}{3}}{\Big )}&{\text{if }}x\equiv 1{\pmod {3}},\\0^{\infty }\;1\;{\textrm {Z>}}\;01\;001^{(x+1)/3}\;1\;0^{\infty }&{\text{if }}x\equiv 2{\pmod {3}}.\end{cases}}$$

Substituting $x\leftarrow 3x$, $x\leftarrow 3x+1$, and $x\leftarrow 3x+2$ to each of these cases respectively gives us our final result.

Trajectory

The initial blank tape represents $g(0)$, and the Collatz-like rules are iterated 15 times before halting:

An animation of $g(0)$ becoming $g(34)$ in 365 steps (click to view).

$${\begin{array}{|l|}\hline {\begin{array}{lllllllllllllll}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}}$$