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: Failed to parse (syntax error): {\displaystyle 0^\infty \; 11 \; (1 \; (01)^*)^* \; 0011100 \; \text{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

Failed to parse (syntax error): {\displaystyle 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 \; \text{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}f_{0}(x)&=&2x+4\\f_{k+1}(x)&=&f_{k}^{x+2}(0)\\\end{array}}$$

then

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

Bound

Let

Failed to parse (unknown function "\begin{array}"): {\displaystyle \begin{array}{l} a_0 & = & 2 \\ a_{k+1} & = & f_k(a_k) \\ }

then

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

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

Note that $f_{k}(x)=(2\uparrow ^{k}(x+4))-4$ and so for $k\geq 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$.