View source for 1RB2LC1RC 2LC---2RB 2LA0LB0RA

{{machine|1RB2LC1RC_2LC---2RB_2LA0LB0RA}} {{unsolved|Does this TM halt? If so, how many steps does it take to halt?}}
{{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}} 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: {{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}. 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 [https://discord.com/channels/960643023006490684/1259770474897080380/1259968221218607145 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 [[User:Xl643|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

<pre>
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
</pre>

{| class="wikitable"
! From !! To
|-
| A<sub>1</sub>(0, b, 2n) || A<sub>2</sub>(1, b+2n+1, 0)
|-
| A<sub>1</sub>(0, b, 2n+1) || A<sub>1</sub>(1, 0, b+2n+3)
|-
| A<sub>1</sub>(m+1, b, 0) || A<sub>1</sub>(m, 0, b+2)
|-
| A<sub>1</sub>(m+1, b, n+1) || A<sub>2</sub>(m, b+1, n)
|-
| A<sub>2</sub>(0, b, 2n) || A<sub>1</sub>(2b+3, 0, 2n+1)
|-
| A<sub>2</sub>(0, b, 2n+1) || A<sub>2</sub>(2b+3, 2n+1, 0)
|-
| A<sub>2</sub>(m+1, b, 0) || B(m, b+2)
|-
| A<sub>2</sub>(m+1, b, n+1) || A<sub>1</sub>(m, b+2, n)
|-
| B(0, b) || Halt
|-
| B(m+1, 2n) || A<sub>2</sub>(m, 2n+1, 0)
|-
| B(m+1, 2n+1) || A<sub>1</sub>(m, 0, 2n+3)
|}
Starting from A<sub>1</sub>(0, 0, 1) (at step 2).

== savask's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1254085725138190336

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

<pre>
(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)
</pre>

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

<pre>
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
</pre>

== 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: 

<pre>
  (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)
</pre>

=== Phases ===
We can think of this going through two different phases. "Even Phase" (where <code>a</code> is even) and "Odd Phase" (where <code>a</code> is odd).

<pre>
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)
</pre>

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 <code>a</code> is bigger or smaller, then "Odd Phase" will end going back to "Even Phase" again.

=== Repeated (0, b, 2c) ===

Let <math>f(n) = 3n+4</math>, then<math display="block">(0, b, 2c) \to (0, f(b), 2(c - b - 1))</math> Let<math display="block">h(n) = f^n(1) + 1 = 3^{n+1} - 1</math><math display="block">g(n) = \sum_{k=0}^{n-1} h(k) = \frac{3}{2} (3^n - 1) - n</math>


Then if <math>c > g(n)</math>:<math display="block">(0, 1, 2c) \to (0, f^n(1), 2 (c-g(n))) \to (2 h(n), 1, 2 (c-g(n)))</math>

=== Repeated (0, 1, 2c) ===
https://discord.com/channels/960643023006490684/1084047886494470185/1254635277020954705

Let <math>C(n) = (0, 1, 2n)</math> = <code>0^inf 1 <A2 22 (20)^2n 0^inf</code>
    
<math display="block">C(g(n) + 8k+1) \to C(g(n) + 8k+1 + n+9)</math><math display="block">\forall k: \frac{h(n) - 45}{65} < k < \frac{h(n) - 22}{38}</math>

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

Ex: if n = 7, then we get:<math display="block">\forall k \in [101, 172]: C(3273 + 8k) \to C(3273 + 8(k+2))</math>


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

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

== A(a, c) Rules and Timings ==

Let A(a, c) = A<sub>1</sub>(a, 0, c) = <code>0^∞ 1 2^a <C (20)^c 0^∞</code>, where A<sub>1</sub>(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.

{| class="wikitable" style="text-align:left"
|+ Rules and associated step counts ([https://discord.com/channels/960643023006490684/1259770474897080380/1324065684677988505 source])
! !! style="text-align:left" | A(a, c) → !! Conditions !! Step count
|-
! style="text-align:right" | (a)
| A(a−c−1, 3c/2+2) || c ≤ a−1, c ≡ 0 (mod 2) || 3c<sup>2</sup>+8c+5
|-
! style="text-align:right" | (b)
| A(a−c−2, 3(c−1)/2+5) || c ≤ a−2, c ≡ 1 (mod 4) || (6c<sup>2</sup>+31c+37)/2
|-
! style="text-align:right" | (c)
| A(a−c−4, 3(c−1)/2+8) || c ≤ a−4, c ≡ 3 (mod 4) || 3c<sup>2</sup>+29c+65
|-
! style="text-align:right" | (d)
| Halt(3(c−1)/2+7) || c = a−3, c ≡ 3 (mod 4) || (6c<sup>2</sup>+43c+75)/2
|-
! style="text-align:right" | (e)
| A(3c+8, 1) || c = a−2, c ≡ 3 (mod 4) || (6c<sup>2</sup>+37c+63)/2
|-
! style="text-align:right" | (f)
| Halt(3(c−1)/2+4) || c = a−1, c ≡ 1 (mod 2) || 3c<sup>2</sup>+8c+6
|-
! style="text-align:right" | (g)
| Halt(a/2+c+4) || c ≥ a, a ≡ 0, c ≡ 0 (mod 2) || 3a<sup>2</sup>+5a+9c+24
|-
! style="text-align:right" | (h)
| A(1, a/2+c+2) || c ≥ a, a ≡ 0, c ≡ 1 (mod 2) || 3a<sup>2</sup>+3a+5c+11
|-
! style="text-align:right" | (i)
| A(3a, c−a+4) || c ≥ a, a ≡ 1, c ≡ 0 (mod 2) || 3a<sup>2</sup>−9a+14c+30
|-
! style="text-align:right" | (j)
| A(3a+2, c−a+1) || c ≥ a, a ≡ 1, c ≡ 1 (mod 2) || 3a<sup>2</sup>+5c+6
|}

== Equivalence to 1RB0LB0RC_2LC2LA1RA_1RA1LC--- ==
{{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}, #153, eventually becomes equivalent to this machine. As found by [https://discord.com/channels/960643023006490684/1259770474897080380/1260244842999709726 @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 ([https://discord.com/channels/960643023006490684/1259770474897080380/1367340727859679322 Discord link]):

# The machine (and its sibling) pass straight through various rounds of cleverly-written deciders
# dyuan posts his set of rules and looks into it a bit, Justin notes that he'd briefly looked at it some time back
# 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
# I take a crack at it myself, this time in terms of chains starting from <code>A(1,c)</code> configs, find some <code>c</code> 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 <code>c</code> value
# dyuan and I nail down the ideas of 'halter families' (collections of infinitely many halting <code>c</code> values so we don't have to brute-force them) and 'reachability analysis' (obtaining a strong probvious guess of whether a <code>c</code> value will or won't occur in the machine's actual forward behavior, assuming it hasn't halted beforehand)
# dyuan and I race to find a halting <code>c</code> 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)
# By dint of a somewhat more performant program, I find (and dyuan confirms) the <math>c = \frac{3^{307}-8\,282\,708\,212}{13\,959\,275}</math> we all know and love, probviously sealing the machine's fate
[[Category:Cryptids]]