1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC

A probviously halting BB(6) Cryptid found by @mxdys on 30 Jun 2024.

Analysis by Shawn Ligocki:

1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC

C(a, b, c) = $ 1^2a+1 C> 0^2b 1^c 01 $

Level 1:
  C(a, b+2, c) -> C(a+3, b, c)
  C(a, 1, c+2) -> C(1, a+3, c)
  C(a, 0, c+1) -> C(1, a+1, c)

  C(a, 0, 0) -> C(1, 2, 2a+3)
  C(a, 1, 1) -> C(1, 2, 2a+7)
  C(a, 1, 0) -> Halt(2a+5)

Level 2:
  C(1, 2b,   c+1) -> C(1, 3b+2, c)
  C(1, 2b+1, c+2) -> C(1, 3b+4, c)

  C(1, 2b,   0) -> C(1, 2, 6b+5)
  C(1, 2b+1, 1) -> C(1, 2, 6b+9)
  C(1, 2b+1, 0) -> Halt(6b+7)


C(1, 0, 0)  @11
C(1, 2, 5)  @55
  ...
C(1, 17, 1)
C(1, 2, 57)
  ...
C(1, 70_091_065, 1)
C(1, 2, 210_273_201)
  ...

Rules validated in https://github.com/sligocki/busy-beaver/blob/main/rust/src/validator.rs#L1042

For my code I'm seeing O(n^2) runtime:

          0  C(1, 2, 5)  [0s]
          4  C(1, 2, 57)  [0s]
         45  C(1, 2, 210_273_201)  [0s]
    100_000  C(1, 10^17_602, 210_123_530)  [1s]
    200_000  C(1, 10^35_211, 209_973_408)  [4s]
    300_000  C(1, 10^52_820, 209_823_652)  [10s]
    400_000  C(1, 10^70_429, 209_673_652)  [17s]
    500_000  C(1, 10^88_039, 209_523_616)  [27s]
    600_000  C(1, 10^105_648, 209_373_548)  [38s]
    700_000  C(1, 10^123_257, 209_223_420)  [52s]
    800_000  C(1, 10^140_866, 209_073_477)  [68s]
    900_000  C(1, 10^158_475, 208_923_310)  [86s]
  1_000_000  C(1, 10^176_084, 208_773_236)  [107s]

ETA maybe 22 days for next "reset" (c <= 1).

Interestingly, both of the 2 reset's I've been able to simulate to both follow the C(1, 2b+1, 1) -> C(1, 2, 6b+9) path.

Equivalent TMs

These 6 TMs all have the exact identical tape behavior:

1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA1LD_---0LC   1RA 1LD 1LD
1RB1RA_0RC1RC_1RD0LF_0LE1LE_1RA1LD_---0LC   1RA 1RD 1LD
1RB0RD_0RC1RC_1LD0LF_0LE1LE_1RA1LD_---0LC   0RD 1LD 1LD
1RB0RD_0RC1RC_1RD0LF_0LE1LE_1RA1LD_---0LC   0RD 1RD 1LD
1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC   1RA 1LD 0LB
1RB0RD_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC   0RD 1LD 0LB

The one mxdys first shared: 1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA1LD_---0LC is the most efficient and all the rest add extra steps during certain transitions. IIUC, the others would all have been pruned using Marxen's pruning algorithm. Specifically, these are all the options by changing:

A2 -> {1RA,0RD}
C0 -> {1LD,1RD}
E1 -> {1LD,0LB}

Except that you cannot have both C0->1RD and E1->0LB They are all equivalent b/c:

1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA1LD_---0LC
  vs. 1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC
    {E1->0LB, Bx->xRC, C0->1LD} == E1->1LD
  vs. 1RB1RA_0RC1RC_1RD0LF_0LE1LE_1RA1LD_---0LC
    {C0->1RD, Dx->xLE, E1->1LD} == C0->1LD
  vs. 1RB0RD_0RC1RC_1LD0LF_0LE1LE_1RA1LD_---0LC
    {A1->0RD, Dx->xLE, E0->1RA} == A1->1RA

I believe that this means that either

1RB0RD_0RC1RC_1RD0LF_0LE1LE_1RA1LD_---0LC   0RD 1RD 1LD
1RB0RD_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC   0RD 1LD 0LB

will be the longest running depending on whether there are more E1 or C0 transitions in 1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA1LD_---0LC's complete transition history.