1RB1RA_1RC0LC_0LD1LG_1LF0LE_1RZ1LF_0LA1LD_1RA1LC
1RB1RA_1RC0LC_0LD1LG_1LF0LE_1RZ1LF_0LA1LD_1RA1LC (bbch) is a halting tetrational BB(7) TM that runs for over 10↑↑35 steps found by Shawn Ligocki on 8 May 2025 based on @mxdys's enumeration system https://github.com/ccz181078/TM.
Analysis by Shawn Ligocki:
1RB1RA_1RC0LC_0LD1LG_1LF0LE_1RZ1LF_0LA1LD_1RA1LC B(a,b,c,d) = 0^inf 1^a B> 1^b 01^c 011^d 0^inf D(a) = B(a,0,0,0) = 0^inf 1^a B> 0^inf D(3k) -> Halt(2k+1) D(9k+1) --> D(32 2^k - 27) D(9k+4) --> D(32 2^k - 23) D(9k+7) --> D(32 2^k - 18) D(9k+2) --> D(34 2^k - 27) D(9k+5) --> D(34 2^k - 23) D(9k+8) --> D(34 2^k - 18) Start: D(1)
Basic transitions used to build this:
0 1^2n+1 B> 1 --> 1^2n+3 B> 0 1^2n+1 B> 0 1^m 0 --> 1^2n+m+4 B> for m >= 1 0^4 1^2n B> 1 --> 1 B> 010 1^2n 0 0^5 1^2n B> 1 --> 1^5 B> 1^2n 0 0 1^3k B> 00 --> 1 Z> 011^k 00 0^2 1^3k+1 B> 00 --> 1 B> 01 011^k 00 0^3 1^3k+2 B> 00 --> 1 B> 0111 011^k 00 $ 1^a B> 011^3 --> $ 1^2a+23 B> (for a odd)
Model
At first it might appear that there is a 1/3 chance of halting each iteration, but in fact, that is not quite right since only they 9k+4 and 9k+5 rules can possibly lead to a halt. Based on manual simulation it appears that the chance of halting each turn reaches a steady state of about 1/7.85. Legion suggested this model: Consider all remainders mod 18 and all the remainders mod 18 that they can lead to:
0 -> halt 1 -> 5,11,17 2 -> 1,7,13 3 -> halt 4 -> 3,9,15 5 -> 5,11,17 6 -> halt 7 -> 2,8,14 8 -> 4,10,16 9 -> halt 10 -> 1,7,13 11 -> 5,11,17 12 -> halt 13 -> 5,11,17 14 -> 3,9,15 15 -> halt 16 -> 4,10,16 17 -> 2,8,14
(all weights equal) with stationary distribution (0, 1/18*(3-sqrt(5)), 1/18*(-1+sqrt(5)), 1/18*(3-sqrt(5)), 1/18*(3-sqrt(5)), 1/9*(-1+sqrt(5)), 0, 1/18*(3-sqrt(5)), 1/18*(-1+sqrt(5)), 1/18*(3-sqrt(5)), 1/18*(3-sqrt(5)), 1/9*(-1+sqrt(5)), 0, 1/18*(3-sqrt(5)), 1/18*(-1+sqrt(5)), 1/18*(3-sqrt(5)), 1/18*(3-sqrt(5)), 1/9*(-1+sqrt(5))), halting probability 1/6*(3-sqrt(5)) ≈ 0.12732, and expected lifetime 3/2*(3+sqrt(5)) ≈ 7.8541.
This model can be simplified to the Markov Chain:
A->A,A,B B->A,B,H
Where here A represents any value = 1,5 (mod 6), B any value = 2,4 (mod 6) and H any value = 3 (mod 6) (which will lead to halt next turn).