1RB--- 0RC0RE 1RD1RF 1LE0LB 1RC0LD 1RC1RA

Unsolved problem:

Does this TM halt? If so, how many steps does it take to halt?

1RB---_0RC0RE_1RD1RF_1LE0LB_1RC0LD_1RC1RA (bbch) is a probviously halting BB(6) Cryptid found by Racheline on 23 November 2024 (Discord link). It has an interesting halting mechanism.

`1RB---_0RC0RE_1RD1RF_1LE0LB_1RC0LD_1RC1RA` is a probviously halting cryptid. just an exponential one, specifically at each step it simply multiplies the main number by 8/3 and then changes a few things depending on what it was mod 3. the left side can change in a few ways to store information between these steps. if you start from the empty left side, there are some sequences of numbers you can get mod 3 which make the TM halt, and if the main number mod 3 was random, then the probability of this eventually happening would be 1 regardless of how long those sequences are. this is all standard stuff.

however
i'm pretty sure the shortest such sequence has length around 100. i think it's a fun puzzle to try to find one yourself. the shortest one i found on my own has length 110, though it's actually a group of 2^13\*3^15 = 117546246144 such sequences because some parts can be permuted with certain restrictions. specifically, each (n,m) in the following sequence of pairs can be replaced with any sequence of n 2's and m 0's whose first k elements contain at least k/3 2's for every k<=n+m:
||(1,0), (2,1), (1,0), (2,3), (1,0), (2,4), (1,0), (2,3), (1,0), (3,5), (1,0), (3,4), (1,0), (3,3), (1,0), (2,4), (1,0), (2,3), (1,0), (3,4), (1,0), (3,6), (1,0), (2,3), (1,0), (3,4), (1,0), (3,6), (1,0)|| (spoilered because i think it's a relatively fun puzzle to try to figure out on your own)
for any given point at which the left side is empty, the probability that it will follow one of these sequences from that point is just above 1/3^87
i also ran a search on all sequences of only 0's and 2's (1's seem to always reset most of the progress you made in getting to a halting config so i ignored those) up to that length, and the shortest it found was length 107, so the only way it's less than that would be if either my code is wrong or somehow 1's manage to be useful for something other than resetting.

so i think it's pretty reasonable to guess that from a given position with empty left side, the probability that the TM will halt before resetting the left side is around 1/3^80. the rest of the computation is the same as always: the expected number of times we generate a new random number mod 3 should be around 3^80, and since that happens only when the main number is roughly multiplied by 8/3, the number of 1s when halting should be around (8/3)^3^80 ≈ 10^10^37.8, and the halting time should be around (that)^2, i.e. around 10^10^38.1
i know, not that impressive compared to the current champion, but i'm posting it because i like the mechanism. also i guess it would still be in 11th place if this approximation is correct, though the current 11th place TM takes around 10^10^35.3 steps to halt so it's kinda close.