1RB0RB_1LC1RE_1LF0LD_1RA1LD_1RC1RB_---1LC

Unsolved problem:

Does this TM run forever?

1RB0RB_1LC1RE_1LF0LD_1RA1LD_1RC1RB_---1LC (bbch) is a probviously non-halting 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)

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

Rule QP1:  Q(1,2b+1) -> P(3b+8)
Rule Q1:   Q(1,2b)   -> Q(b+2,1)

Rule QP2:  Q(2a+3,b) -> P(b+5a+6)
Rule Q2:   Q(2a+2,b) -> Q(a,b+2a+5)

Rule QH:   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 rules have been proven in Lean.

Rule dispatch for 1RB0RB 1LC1RE 1LF0LD 1RA1LD 1RC1RB

The TM will halt after N iterations of the map Q if it ever takes the form $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.

Q(1, 0) has no predecessors in the map, it cannot be reached. Reachable Q-states always have b ≥ 1 (Stronger: b = 1 or b ≥ 5).

The backward chain to Q(0, b) is:

  Q(0, b)  ← Q(2, b')  where b = b'+5
  Q(2, b') ← Q(6, b'') where b' = b''+9
  Q(6, ·)  ← Q(14, ·)  ← Q(30, ·)  ← Q(62, ·)  ← ...

General pattern: Q(2^(n+1) − 2, ·) chains down to Q(0, ·) through n halvings, all intermediate values being even.

The alternative path to Q(6, ·) is: Q(4, b) → Q(1, b+7) → Q((b+7)/2 + 2, 1) when b+7 is even (b odd), which gives Q(6, 1) when b = 1, i.e., Q(4, 1) → Q(1, 8) → Q(6, 1) → halt.

The P map

${\displaystyle }$ Since there is only one way the P phase can be left, it can be written as a function / map: $$p(n)=\{\begin{array}{ll}p\left(\frac{3n+8}{2}\right)& \text{even }n,\\ \frac{n+3}{2}& \text{odd }n,\end{array}$$ where $p(n)$ enters $Q$ using Rule PQ. The recursive function is equivalent to: $$p(n)=\frac{(n+8)(\frac{3}{2}{)}^{{\nu }_2(n+8)}-5}{2}.$$ Fixing the exponent, we get an infinite set of defining equations for $p(n)$, $$p(n)=\{\begin{array}{ll}\frac{n+3}{2},& \text{odd }n,\\ \frac{3n/2+7}{2},& n+8=2m,m\text{ odd}\\ \frac{9n/4+13}{2},& n+8=4m,m\text{ odd}\\ \frac{27n/8+22}{2},& n+8=8m,m\text{ odd}\\ \dots \end{array}$$ A natural question to ask, since $Q$ needs $2^i-2$ as first argument to halt, is when is $p(n)=2^i-2$? With the above definitions this leads to the infinite set of Diophantine equations: $$\begin{array}{rlrlr}n& =2^{i+1}-7,& & & n=\{9,25,57,121,249,505,1017,2041,4089,\dots \}\\ 3n& =2^{i+2}-22,& n=2m-8,m\text{ odd}& \to n=\frac{2^{2i}-22}{3}& =\{14,78,334,1358,5454,21838,87374,349518,\dots \}\\ 9n& =2^{i+3}-68,& n=4m-8,m\text{ odd}& \to n=\frac{2^{6i+5}-68}{9}& =\{220,14556,932060,59652316,\dots \}\\ 27n& =2^{i+4}-216,& n=8m-8,m\text{ odd}& \to \text{No solution.}& \\ 81n& =2^{i+5}+1,& n=8m-8,m\text{ odd}& \to \text{No solution.}& \\ \dots & & \end{array}$$ The start of a table of values where $p(n)=2^i-2$

n       p(n) = 2^i-2
9          6
14         14
25         14
57         30
78         62
121        62
144        254
220        254
249        126
334        254
505        254
1017       510
1358       1022
2041       1022
4089       2046
5454       4094
8185       4094
14556      16382

Is Q(1, _) reachable?

The other way to halt is the Q(1,_) path but, when simulating the first $10^6$ rule steps, the machine never reaches a Q(1,_) state. For that, the PQ rule would have to output Q(4,_), or Q2 would have to output Q(4,_). The latter happens when we have Q(x,_) with $x=3\cdot 2^i-2,i\ge 1$. So, ultimately there is a second system of Diophantine equations that could tell us for which input to P, PQ outputs a Q state that leads to Q(1,_).