0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD

0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch) is a halting BB(4,3) machine that appears to run for around

$$2\uparrow \uparrow \uparrow (2^{2^{32}+1})$$

steps. The TM was discovered by Pavel Kropitz in May 2024 as a group of 6 long-running halting BB(4,3) TMs. Racheline analyzed the machine by hand in Feb 2025, validating the result and provided the step estimate listed above.

Pavel listed the halting tape as:

1 2^((80*2^((<(8*2^((8*2^(29) - 2)) - 5); (<(80*2^((b - 10)/5) - 17)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> + 4); (<(80*2^((<(80*2^((8*2^((8*2^(29) - 2)) - 3)) - 13)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> - 6)/5) - 17)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> + 4)> - 10)/5) - 3)) 1 0 1 2 1^2 Z> 1 2^2 1

Analysis by racheline

https://discord.com/channels/960643023006490684/1331570843829932063/1337228898068463718

f(n) = 2^2^(n+1)
g(n) = (5*2^(2^(f^n(0)+1)+2)-8)/9
n0 = (5*2^(2^(2^32+1)+1)-4)/9
n1 = 2^(2^32+1)-4
0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD halts with 5*2^(2^(f^g^n1(n0)(0)+1)+2)+7 nonzero symbols on the tape, after roughly (that)^2 steps
that's around 2^^^(2^(2^32+1)-1)
the rules necessary for verification:
0^inf 1 <D 0^(5n) 2^4 ->
0^inf 1 <D 0^(5*2^n+2)

0^inf 1 <D 0^(5n+2) 2^5 ->
0^inf 1 <D 0^(5*2^(n+1))

0^inf 1 <D 0^(5n) 221122 ->
0^inf 1 <D 0^(5*2^n+4)

0^inf 1 <D 0^(5n+4) 1 0^5 ->
0^inf 1 <D 0^2 2^23 1 0^(5*2^(n+2)-22) 1011221

0^inf 1 <D 0^(5n) 1 0^10 ->
0^inf 1 <D 0^2 2^(5*2^(n+1)) 11221

0^inf 1 <D 0^(5n+2) 2222112 ->
0^inf 1 <D 0^(5*2^(n+1)+2)

0^inf 1 <D 0^(5n+2) 21 0^10 ->
0^inf 1 <D 0^2 2^(5*2^(n+2)-4) 11221

0^inf 1 <D 0^(5n+2) 2^9 ->
0^inf 1 <D 0^(5*2^(n+1)) 2^4 ->
0^inf 1 <D 0^(5*2^2^(n+1)+2) =
0^inf 1 <D 0^(5f(n)+2)

0^inf 1 <D 0^2 2^(9n) ->
0^inf 1 <D 0^(5f^n(0)+2)

0^inf 1 <D 0^2 2^(9n+4) 11221 0^10 ->
0^inf 1 <D 0^(5f^n(0)+2) 222211221 0^10 ->
0^inf 1 <D 0^(5*2^(f^n(0)+1)+2) 21 ->
0^inf 1 <D 0^2 2^(5*2^(2^(f^n(0)+1)+2)-4) 11221 =
0^inf 1 <D 0^2 2^(9g(n)+4) 11221

0^inf 1 <D 0^2 2^(9n+4) 11221 0^(10m) ->
0^inf 1 <D 0^2 2^(9g^m(n)+4) 11221

0^inf 1 <D 0^2 2^16 11221 0^inf
0^inf 1 <D 0^10 2^11 11221 0^inf
0^inf 1 <D 0^22 2^7 11221 0^inf
0^inf 1 <D 0^160 2211221 0^inf
0^inf 1 <D 0^(5*2^32+4) 1 0^inf
0^inf 1 <D 0^2 2^23 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^10 2^18 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^22 2^14 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^160 2^9 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^(5*2^32+2) 2^5 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^(5*2^(2^32+1)) 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^2 2^(5*2^(2^(2^32+1)+1)) 11221 0^(5*2^(2^32+2)-32) 1011221 0^inf =
0^inf 1 <D 0^2 2^(9n0+4) 11221 0^(10n1+8) 1011221 0^inf
0^inf 1 <D 0^2 2^(9g^n1(n0)+4) 11221 0^8 1011221 0^inf
0^inf 1 <D 0^(5*2^(f^g^n1(n0)(0)+1)+2) 21 0^8 1011221 0^inf
this continues the same way as if the 0^8 was a 0^10 until the last few steps, so the tape differs from 0^inf 1 <D 0^2 2^(5*2^(2^(f^g^n1(n0)(0)+1)+2)-4) 11221 in a small amount of symbols on the left end and the right end, which you can easily count by running a smaller example

Equivalent TMs

The TMs 0RB1RZ1RC_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch), 1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ0RA (bbch), 1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ1RB (bbch) are equivalent to 0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch), with the exact same halting configuration 0^inf 1 2^(σ-10) 101211 Z> 1221 0^inf, where σ = 5*2^(2^(f^g^n1(n0)(0)+1)+2)+7 is the total number of nonzero symbols.

To see that 0RB1RZ1RC_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch) is equivalent, simply notice that the situation A> 20 never occurs in any of the rules in the above analysis, or inside the low-level bell cycles, and that A> 21 and A> 22 behave the same in both TMs, except that they take two more steps in 0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch). Since the A2 transition is the only difference between the two, this means the TMs only differ in the number of steps it takes to halt (and even that difference is insignificant, on the order of σ = 5*2^(2^(f^g^n1(n0)(0)+1)+2)+7 while the total number of steps is around σ²). 1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ0RA (bbch) and 1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ1RB (bbch) are just 0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch) and 0RB1RZ1RC_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch) respectively, but started one step later, so that their halting time is 1 step smaller.