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) is a BB(3,3) holdout which appears to probviously halt. If it 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. After about 1.8 million steps and up to some relabelling, it is equivalent to holdout #153: 1RB0LB0RC_2LC2LA1RA_1RA1LC--- (bbch). And if you start in state C it is a permutation of the same machine. Together, they simulate 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".

The user Xl643 Calls this Turing machine Smallfoot.

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.

A(a, c) Rules and Timings

Let A(a, c) = A₁(a, 0, c) = 0^∞ 1 2^a <C (20)^c 0^∞, where A₁(a, b, c) comes from dyuan01's rules. Then the TM satisfies the following rules once it reaches A(0, 1) after 2 steps. Note that rules (a) and (g) aren't actually reachable from the initial condition.

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

Equivalence to 1RB0LB0RC_2LC2LA1RA_1RA1LC---

1RB0LB0RC_2LC2LA1RA_1RA1LC--- (bbch), #153, eventually becomes equivalent to this machine. As found by @Legion, after running the #153 machine for 1,790,901 steps, if one permutes the states A,C, and B and exchanges 1 for 2 and L for R, it has the same configuration as TM #758 after it has run 1,841,608 steps.

History

LegionMammal's rough timeline of this TM on 30 Apr 2025 (Discord link):

1. The machine (and its sibling) pass straight through various rounds of cleverly-written deciders
2. dyuan posts his set of rules and looks into it a bit, Justin notes that he'd briefly looked at it some time back
3. Shawn and savask write up some acceleration schemes, find empirical evidence that it repeatedly comes close to halting, and speculate that it may actually halt after some period of time
4. I take a crack at it myself, this time in terms of chains starting from A(1,c) configs, find some c values leading to a halt (showing that there's no obvious structural barrier), and conjecture some heuristics for how long it should take to reach such a halting c value
5. dyuan and I nail down the ideas of 'halter families' (collections of infinitely many halting c values so we don't have to brute-force them) and 'reachability analysis' (obtaining a strong probvious guess of whether a c value will or won't occur in the machine's actual forward behavior, assuming it hasn't halted beforehand)
6. dyuan and I race to find a halting c value that 'explodes' (passes the reachability analysis), first within the 'trivial' halter family to no avail, then within all halter families (writing a program to enumerate halter families is extremely fiddly, at this point I treat some of my own code as a black box not to be touched)
7. By dint of a somewhat more performant program, I find (and dyuan confirms) the $c={\frac {3^{307}-8\,282\,708\,212}{13\,959\,275}}$ we all know and love, probviously sealing the machine's fate