1RB2LC1RC 2LC---2RB 2LA0LB0RA

Unsolved problem:

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

1RB2LC1RC_2LC---2RB_2LA0LB0RA (bbch)

This is a BB(3,3) holdout which appears to probviously halt. If can be proven to halt, it will be the BB(3,3) champion, in terms of both steps and tape symbols. However, it could also turn out to be a probviously halting Cryptid.

This is holdout #758 on Justin's 3x3 mugshots. And if you start in state C it is a permutation of #153: 1RB0LB0RC_2LC2LA1RA_1RA1LC--- (bbch). It simulates a complex set of Collatz-like rules with two decreasing parameters.

After active exploration on the #bb3x3 channel by LegionMammal and dyuan, LegionMammal found (and dyuan confirmed) a configuration A(1,c) (defined here) which halts and for which a huge "wall" of previous A(1, c') values all reach it. This gives strong evidence that the TM probviosly halts since jumping over this wall is very "unlikely".

NOTE: As of 16 Jul 2024 there is a lot more active work on the #bb3x3 channel with LegionMammal and dyuan not reflected here.

dyuan01's Rules

https://discord.com/channels/960643023006490684/1084047886494470185/1224457633176486041

A_1(a, b, c) = 0^inf 1 2^a <C (22)^b (20)^c 0^inf
A_2(a, b, c) = 0^inf 1 2^a <A2 (22)^b (20)^c 0^inf
B(a, b) = 0^inf 1 2^a <B0 (20)^b 0^inf

From	To
A1(0, b, 2n)	A2(1, b+2n+1, 0)
A1(0, b, 2n+1)	A1(1, 0, b+2n+3)
A1(m+1, b, 0)	A1(m, 0, b+2)
A1(m+1, b, n+1)	A2(m, b+1, n)
A2(0, b, 2n)	A1(2b+3, 0, 2n+1)
A2(0, b, 2n+1)	A2(2b+3, 2n+1, 0)
A2(m+1, b, 0)	B(m, b+2)
A2(m+1, b, n+1)	A1(m, b+2, n)
B(0, b)	Halt
B(m+1, 2n)	A2(m, 2n+1, 0)
B(m+1, 2n+1)	A1(m, 0, 2n+3)

Starting from A₁(0, 0, 1) (at step 2).

savask's Rules

https://discord.com/channels/960643023006490684/1084047886494470185/1254085725138190336

Let (m, b, n) = A2(m, b, n) = 0^inf 1 2^m <A2 (22)^b (20)^n 0^inf

(0, b, n) -> (2b+2, 1, n) if n is even
          -> (2b, 1, n+3) if n is odd

(1, b, 0) -> Halt

(2, b, 0) -> (0, b+3, 0) if b is even
          -> (0, 1, b+5) if b is odd

(m, b, 0) -> (m-2, b+3, 0) if b is even
          -> (m-3, 1, b+3) if b is odd

(1, b, n) -> (0, 1, n+b+2) if n is even
          -> Halt if n is odd

(2, b, 1) -> Halt if b is even
          -> (0, 1, b+5) if b is odd

(m, b, 1) -> (m-3, 1, b+3)

(m, b, n) -> (m-2, b+3, n-2)

https://discord.com/channels/960643023006490684/1084047886494470185/1254306301786198116

step (A2 0 b n) | even n = A2 (2*b+2) 1 n
                | otherwise = A2 (2*b) 1 (n+3)
-- From now on m > 0
step (A2 1 b 0) = error $ "Halt A2 1 " ++ show b ++ " 0"
step (A2 2 b 0) | even b = A2 0 (b+3) 0
                | otherwise = A2 0 1 (b+5)
step (A2 m b 0) | even b = A2 (m-2) (b+3) 0
                | otherwise = A2 (m-3) 1 (b+3)
-- From now on n > 0
step (A2 1 b n) | even n = A2 0 1 (n+b+2)
                | otherwise = error $ "Halt A2 1 " ++ show b ++ " " ++ show n
step (A2 2 b 1) | even b = error $ "Halt A2 2 " ++ show b ++ " 1"
                | otherwise = A2 0 1 (b+5)
step (A2 m b 1) = A2 (m-3) 1 (b+3)
-- Here m > 1, n > 1
step (A2 m b n) = let d2 = (min m n) `div` 2 in A2 (m - 2*d2) (b + 3*d2) (n - 2*d2) -- Accelerated

Shawn's Rules

https://discord.com/channels/960643023006490684/1084047886494470185/1254307091863048264

We can reduce the set of rules from savask's list a bit by noticing that we can evaluate so that all rules end with c even:

  (0, b, 2c)    -> (2b+2, 1, 2c)

  (1, b, 0) -> Halt
  (1, 2b,   2c)  -> (0, 1, 2(b+c+1))
  (1, 2b+1, 2c)  -> (2, 1, 2(b+c+3))

  (a, 2b,   0)  -> (a-2, 2b+3, 0)
  (2, 2b+1, 0)  -> (0, 1, 2b+6)
  (a, 2b+1, 0)  -> (a-3, 1, 2b+4)

  (a, b, c) -> (a-2, b+3, c-2)

Phases

We can think of this going through two different phases. "Even Phase" (where a is even) and "Odd Phase" (where a is odd).

Even Phase: a,c even:
  (0, b, 2c) -> (2b+2, 1, 2c)
  (2a+2, 2b, 0) -> (2a, 2b+3, 0)
  (2, 2b+1, 0) -> (0, 1, 2(b+3))

  To Odd Phase:
    (2a+4, 2b+1, 0) -> (2a+1, 1, 2b+4)
 
Odd Phase: a odd, c even
  To Halt:
    (1, b, 0) -> Halt
    (3, 2b, 0) -> (1, 2b+3, 0) -> Halt

  To Even Phase:
    (1, 2b, 2c+2) -> (0, 1, 2(b+c+2))
    (1, 2b+1, 2c+2) -> (0, 1, 2b+2c+5) -> (2, 1, 2(b+c+4))
    
    (2a+5, 2b, 0) -> (2a+3, 2b+3, 0) -> (2a, 1, 2b+6)
    (2a+3, 2b+1, 0)  -> (2a, 1, 2b+4)

So the only way for this to halt is if it is in "Even Phase" and hits (2k+8, 2k+1, 0) or (4k+12, 4k+3, 0) (which will lead to (1, b, 0) or (3, 2b, 0) eventually). If a is bigger or smaller, then "Odd Phase" will end going back to "Even Phase" again.

Repeated (0, b, 2c)

Let $f(n)=3n+4$, then

$$(0,b,2c)\to (0,f(b),2(c-b-1))$$

Let

$$h(n)=f^{n}(1)+1=3^{n+1}-1$$

$$g(n)=\sum _{k=0}^{n-1}h(k)={\frac {3}{2}}(3^{n}-1)-n$$

Then if $c>g(n)$:

$$(0,1,2c)\to (0,f^{n}(1),2(c-g(n)))\to (2h(n),1,2(c-g(n)))$$

Repeated (0, 1, 2c)

https://discord.com/channels/960643023006490684/1084047886494470185/1254635277020954705

Let $C(n)=(0,1,2n)$ = 0^inf 1 <A2 22 (20)^2n 0^inf

$$C(g(n)+8k+1)\to C(g(n)+8k+1+n+9)$$

$$\forall k:{\frac {h(n)-45}{65}}<k<{\frac {h(n)-22}{38}}$$

Notably, when 8 divides (n+1) then this rule can potentially be applied repeatedly.

Ex: if n = 7, then we get:

$$\forall k\in [101,172]:C(3273+8k)\to C(3273+8(k+2))$$

And we see this starting with $C(4137)=C(3273+8\cdot 108)$ which repeats this rule until we get to $C(4665)=C(3273+8\cdot 174)$.

And as n gets way bigger, these ranges of repeat will increase exponentially.

Timings

Let A(a, c) = A₁(a, 0, c) = 0^∞ 1 2^a <C (20)^c 0^∞. Then the TM satisfies the following rules once it reaches A(0, 1) after 2 steps. These can be seen as an abbreviation of dyuan01's rules, though note that (a) and (g) aren't actually reachable from the blank tape.

Rules and associated step counts (source)

	A(a, c) →	Conditions	Step count
(a)	A(a−c−1, 3c/2+2)	c ≤ a−1, c ≡ 0 (mod 2)	3c2+8c+5
(b)	A(a−c−2, 3(c−1)/2+5)	c ≤ a−2, c ≡ 1 (mod 4)	(6c2+31c+37)/2
(c)	A(a−c−4, 3(c−1)/2+8)	c ≤ a−4, c ≡ 3 (mod 4)	3c2+29c+65
(d)	Halt(3(c−1)/2+7)	c = a−3, c ≡ 3 (mod 4)	(6c2+43c+75)/2
(e)	A(3c+8, 1)	c = a−2, c ≡ 3 (mod 4)	(6c2+37c+63)/2
(f)	Halt(3(c−1)/2+4)	c = a−1, c ≡ 1 (mod 2)	3c2+8c+6
(g)	Halt(a/2+c+4)	c ≥ a, a ≡ 0, c ≡ 0 (mod 2)	3a2+5a+9c+24
(h)	A(1, a/2+c+2)	c ≥ a, a ≡ 0, c ≡ 1 (mod 2)	3a2+3a+5c+11
(i)	A(3a, c−a+4)	c ≥ a, a ≡ 1, c ≡ 0 (mod 2)	3a2−9a+14c+30
(j)	A(3a+2, c−a+1)	c ≥ a, a ≡ 1, c ≡ 1 (mod 2)	3a2+5c+6