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 ^{11}2\uparrow ^{11}3$ steps.

Analysis by Shawn Ligocki

Consider general configurations matching the regex:

$$0^{\infty }\;11\;(1\;(01)^{*})^{*}\;0011100\;{\textrm {A>}}\;0^{\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^{\infty }\;111\;(01)^{3z+1}\;1\;\cdots \;1(01)^{3c+1}\;1\;(01)^{3b+1}\;1\;(01)^{0}\;1\;(01)^{3a+1}\;0011100\;{\textrm {A>}}\;0^{\infty }$$

and let B(a; [x]*k, y, ...) = $B(a;\underbrace {x,\cdots ,x} _{k},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}{l}g_{0}(x)&=&2x+4\\g_{k+1}(x)&=&g_{k}^{x+2}(0)\\\end{array}}$$

then

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

Bound

Let

$${\begin{array}{l}a_{0}&=&2\\a_{k+1}&=&g_{k}(a_{k})\\\end{array}}$$

then

$$B(a_{0};\underbrace {1,\cdots ,1} _{k})\to B(a_{k},\underbrace {0,\cdots ,0} _{k})\to {\text{Halt}}(3a_{k}+2k+9)$$

and

$${\textrm {Start}}\to B(a_{0};\underbrace {1,\cdots ,1} _{12})$$

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

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

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

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

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