1RB0RB_1LC1RE_1LF0LD_1RA1LD_1RC1RB_---1LC

1RB0RB_1LC1RE_1LF0LD_1RA1LD_1RC1RB_---1LC (bbch)

Potential BB(6) Cryptid found by @mxdys on 18 Aug 2024. Andrew Ducharme forward simulated the combined map (P(x), Q(x,y)) for 10^8 iterations. The TM did not yet halt. After 10^7 iterations, the TM reached a value (x',1) where x' ~ 10^604100, and after 10^8 iterations, it reached a value x ~ 10^(6.04305 x 10^6).

start: P(2)

P(2a)   -> P(3a+4)
P(2a+1) -> Q(a+2,1)

Q(2a+3,b) -> P(b+5a+6)
Q(2a+2,b) -> Q(a,b+2a+5)

Q(1,2b+1) -> P(3b+8)
Q(1,2b)   -> Q(b+2,1)

Q(0,b)    -> halt

P(a) := 0^inf 1^a 011 <D 0^inf
Q(a,b) := 0^inf 1^(2a+1) <D 0 1^b 0^inf

A log-scale plot of all points Q(x,1) in the first 1000 iterations of the map R. Blue dots are the x values, yellow dots are the difference between x and the nearest halting value beneath x, and green dots are the difference between the nearest halting value above x and x.

The TM will halt after N iterations of the map Q if it ever takes the form ${\textstyle Q(2^{N+1}-2,y)}$. This can only occur via P(2a+1) -> Q(a+2,1) or Q(1,2b) -> Q(b+2,1). The figure plots x for all cases (x,1) in the first 1000 iterations of R with a logarithmic scale along the vertical axis. The distance from any halting condition 2^M - 2 is growing exponentially with time, so it is only ever getting harder for this TM to halt.

On the trajectory starting from P(2), the Q(1,y) rules, at least through 10^5 steps, are never triggered. Thus, the implementation of the forward simulation can be made slightly faster (roughly 10% in practice) by, instead of nesting the execution of Q(x,y) within two if statements predicated on x=0 and x=1, only checking if x > 2, applying Q(x,y) if true, and throwing an exception if false.

CoSearch: https://cosearch.bbchallenge.org/contricution/tpxh8d8d