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.}& \\ \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

The Q phase accumulator

Once the orbit enters the Q-phase at $Q(a,1)$, rules Q2 and QP2 apply repeatedly (the first argument halves at each Q2 step, accumulating into the second argument) until the first argument becomes odd, at which point QP2 fires and returns to P. The net effect on the second argument is captured by a one-parameter accumulator, name it $q_{\text{acc}}$. It is recursively defined as $$q_{\text{acc}}(2n)=2n+3+q_{\text{acc}}(n-1),q_{\text{acc}}(2n+1)=5n+1$$ $$q_{\text{acc}}(n)=\{\begin{array}{ll}n+3+q_{\text{acc}}(\frac{n}{2}-1),& \text{even }n,\\ \frac{5n-3}{2},& \text{odd }n.\end{array}$$ The closed form with $v_2$, again, the 2-adic valuation and ${\text{ord}}_2(n)$ the odd part of $n$, shows $q_{\text{acc}}(n)$ can take any value: it is even less restricted than $p(n)$: $$2q_{\text{acc}}(n)+5=4n+2v_2(n+2)+\text{max}({\text{ord}}_2(n+2),3).$$

Probabilistic model for halting

The closed form for $q_{\text{acc}}$ helps with analyzing the growth rate of Q-entry values across successive Q–P–Q cycles. The central result is that every cycle amplifies the Q-entry, with a minimum growth factor of 5/4, which comes from the dominant path: where both the Q-phase and P-phase take the $v_2=0$ aka odd shortcut. For the other parity combinations, the growth factor is strictly larger: $v_2=1$ gives growth ≈ 15/8 = 1.875, $v_2=2$ gives ≈ 45/16 ≈ 2.81, etc. There is no contraction in the Q–P–Q cycle. Since every Q–P–Q cycle grows, the Q-entry values diverge to infinity. We formalise this with a stochastic model that provides quantitative bounds on the probability of hitting specific targets.

We model the 2-adic valuation at each cycle as an independent Bernoulli trial: with probability 1/2 the cycle takes the dominant path ($v_2=0$, growth factor 5/4), and with probability 1/2 it takes the $v_2\ge 1$ path (growth factor ≥ 15/8). Formally, let $\mathrm{\Omega }=\{0,1{\}}^N$ with the product Bernoulli(1/2) measure P. Define the stochastic process $$\begin{array}{rl}{X}_0(\omega )& =x_0\\ X_{n+1}(\omega )& =\{\begin{array}{ll}(5X_n+5)/4& v_2=0\\ (15X_n+25)/8& v_2\ge 1\end{array}\end{array}$$ If the machine reaches a Q-entry of order $10^d$ (with $d\ge 1$) without halting, then the expected number of future near-misses of any target $2^i-2$ is at most $$\frac{5}{10^d\cdot \ln 2}<\frac{8}{10^d}.$$ After 1 million rule steps this number shrinks to $10^{-6\cdot 10^4}$.

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,_).

Since this is the same Q-P-Q process but with the target $3\cdot 2^i-2$, the probability of hitting the entry to Q(1,_) has roughly the same probability as halting.