View source for 0RB1RZ0RB 1RC1LB2LB 1LB2RD1LC 1RA2RC0LD

{{machine|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD}}
{{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}} is a halting [[BB(4,3)]] machine that appears to run for around

<math display="block">2 \uparrow\uparrow\uparrow (2^{2^{32}+1})</math>

steps. The TM was discovered by Pavel Kropitz in May 2024 as a group of 6 long-running halting BB(4,3) TMs.<ref>https://discord.com/channels/960643023006490684/1026577255754903572/1243253180297646120</ref> Racheline analyzed the machine by hand in Feb 2025, validating the result and provided the step estimate listed above.<ref>https://discord.com/channels/960643023006490684/1331570843829932063/1337228898068463718</ref>

Pavel listed the halting tape as:

<pre>
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
</pre>

== Analysis by racheline ==
https://discord.com/channels/960643023006490684/1331570843829932063/1337228898068463718

<pre>
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
</pre>

== Equivalent TMs ==

The TMs {{TM|0RB1RZ1RC_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}}, {{TM|1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ0RA|halt}}, {{TM|1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ1RB|halt}} [https://discord.com/channels/960643023006490684/1331570843829932063/1337236324846927932 are equivalent] to {{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}}, with the exact same halting configuration <code>0^inf 1 2^(σ-10) 101211 Z> 1221 0^inf</code>, where <code>σ = 5*2^(2^(f^g^n1(n0)(0)+1)+2)+7</code> is the total number of nonzero symbols.

To see that {{TM|0RB1RZ1RC_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}} is equivalent, simply notice that the situation <code>A> 20</code> never occurs in any of the rules in the above analysis, or inside the low-level bell cycles, and that <code>A> 21</code> and <code>A> 22</code> behave the same in both TMs, except that they take two more steps in {{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}}. 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 σ = <code>5*2^(2^(f^g^n1(n0)(0)+1)+2)+7</code> while the total number of steps is around σ<sup>2</sup>). {{TM|1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ0RA|halt}} and {{TM|1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ1RB|halt}} are just {{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}} and {{TM|0RB1RZ1RC_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}} respectively, but started one step later, so that their halting time is 1 step smaller.

== References ==
<references />