1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF

1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF (bbch) is a halting BB(7) TM which runs for over $2{\uparrow }^{12}2{\uparrow }^{12}3$ steps.

Analysis by Shawn Ligocki

Consider general configurations matching the regex:

$$0^{\mathrm{\infty }}11(1(01{)}^{*}{)}^{*}0011100\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$$

Low level rules

              01 1 01^n 0011100 A> 00   -->                 1 01^n+2 0011100 A>
           01^3 11 01^n 0011100 A> 0^6  -->            1 01^n+5 1 01 0011100 A>
01^3 (1 01)^k+1 11 01^n 0011100 A> 0^6  -->  1 01^n+6 (1 01)^k 11 01 0011100 A>
 011 (1 01)^k   11 01^n 0011100 A> 0^2  -->  1 Z> 111 01^n+1 00 101^k+2

Mid level rules

Let

$$B(a;b,c,...,z)=0^{\mathrm{\infty }}111(01{)}^{3z+1}1\cdots 1(01{)}^{3c+1}1(01{)}^{3b+1}1(01{)}^{0}1(01{)}^{3a+1}0011100\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$$

and let B(a; [x]*k, y, ...) = $B(a;\underset{k}{\underbrace{x,\cdots ,x}},y,...)$ (In other words, [x]*k represents k repeats of the value x in a config).

then

B(a; b+1, ...) -> B(2a+4; b, ...)
B(a; [0]*k, 0, n+1, ...) -> B(0; [0]*k, a+2, n, ...)
B(a; [0]*k) -> Halt(3a + 2k + 9)

Start at step 8178: B(2, [1]*12)

High level rule

Let

$$\begin{array}{lll}{f}_0(x)& =& 2x+4\\ f_{k+1}(x)& =& f_k^{x+2}(0)\\ \end{array}$$

then

$$B(a;\underset{k}{\underbrace{0,\cdots ,0}},n,...)\to B(f_k^n(a);\underset{k}{\underbrace{0,\cdots ,0}},0,...)$$

Bound

Let

$$\begin{array}{lll}{a}_0& =& 2\\ a_{k+1}& =& f_k(a_k)\\ \end{array}$$

then

$$B(a_0;\underset{k}{\underbrace{1,\cdots ,1}})\to B(a_k,\underset{k}{\underbrace{0,\cdots ,0}})\to \text{Halt}(3a_k+2k+9)$$and

$$\text{<mrow data-mjx-texclass="ORD">Start</mrow>}\to B(a_0;\underset{12}{\underbrace{1,\cdots ,1}})$$

and so this TM halts with a sigma score of $\sigma =3a_{12}+33$

Note that $f_k(x)=(2{\uparrow }^k(x+4))-4$ and so for $k\ge 2$,

$$a_k+4>2{\uparrow }^{k}2{\uparrow }^{k}3$$

and so this TM halts with sigma score $\sigma >2{\uparrow }^{12}2{\uparrow }^{12}3$.

This bound is pretty tight: $\sigma <2{\uparrow }^{12}2{\uparrow }^{12}4$.