1RB0LC_1LC0RD_1LF1LA_1LB1RE_1RB1LE_---0LE

From BusyBeaverWiki
Revision as of 17:53, 24 April 2026 by Polygon (talk | contribs) (Added references section)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
Unsolved problem:
Does this TM halt? If so, how many steps does it take to halt?

1RB0LC_1LC0RD_1LF1LA_1LB1RE_1RB1LE_---0LE (bbch) is a probviously halting tetrational BB(6) Cryptid found by Racheline on 23 Nov 2024 (Discord link).

1RB0LC_1LC0RD_1LF1LA_1LB1RE_1RB1LE_---0LE is a tetrational probviously halting cryptid. the lower bound for when it halts is around 10^10^120395, and with each exponentiation it has a 1/4 chance of halting, so i think the expected halting time is around 10^10^10^10^10^120395 sadly we won't be able to run it any further, it uses the hydra map which we don't have a way to accelerate

On 21 Sep 2025, mxdys has shown that this machine is in an equivalence class of 3 machines:

Some analysis by Opus 4.7 / DrDisentangle

Dominant 3-step cycle E → B → D → E (≈ 16,737 fires per 100k steps). E-runs of length 3 are the modal run, corresponding to the "E sweeps left over exactly two 1s then fires" pattern.

Let [b₁, b₂, ..., bₙ, (1)] denote the tape at an E-turnaround (all observed turnarounds have rightmost block = 1):

    0^inf  1^b₁  0  1^b₂  0  ...  0  1^bₙ  0  1  E>  0  0^inf
E-right-blank events (blocks read L-to-R, rightmost is always 1):

step     6 dt=    6  blocks=[1, 1]
step    26 dt=   20  blocks=[2, 2, 1]
step    76 dt=   50  blocks=[6, 2, 1]
step   190 dt=  114  blocks=[2, 10, 2, 1]
step   752 dt=  562  blocks=[2, 25, 2, 1]
step 18240 dt=17488  blocks=[2, 124, 4, 2, 1]

These events are rare; between consecutive events the machine performs a non-trivial restructure that also grows the active region. Rate of growth is super-linear, consistent with a "shift-overflow counter" character.

In addition to the E-turnaround, the only proven macro-regime configurations are mid-run states used by the bump family:

  • M_Config L K j M — head = 1 on the 2nd cell (from left) of the middle 1-block. Tape shape:
    L  0  1^K  0  1 [E,1]1^j  0  1^M  0  0^inf

(Block 2 has size j + 2. Used as the loop invariant of the 5-step bump cycle.)

  • S_Config L K M — head = 0 on the 0-separator between a size-1 block 2 and block 3. Tape shape:
    L  0  1^K  0  1 [E,0]1^M  0  0^inf

(Post-iteration state, one 5-step bump before the final finish.)

  • R_Config L K — 3-block E-turnaround at blocks [K, 2, 1]:
    L  0  1^K  0  1^2  0  1 [E,0] 0^inf
  • R4_Config L K — 4-block E-turnaround at blocks [2, K, 2, 1]:
    L  0  1^2  0  1^K  0  1^2  0  1 [E,0] 0^inf
--- 5-step bump family (middle block shrinks by 1 per cycle) ---

    Generic form: the head at the 2nd cell of block 2 acts as a
    shift register; each 5-step cycle transfers one 1 from the
    middle block to the left block, via:
      1.  E,1 -> 1LE  (pop 1 from left of head)
      2.  E,1 -> 1LE  (pop the block-1/block-2 boundary 1)
      3.  E,0 -> 1RB  (extend left block by 1, now on 1)
      4.  B,1 -> 0RD  (write new 0 separator)
      5.  D,1 -> 1RE  (re-enter E-state)

    All rules in this family hold for any L : Side (fully local).

Bump5:   M_Config L K (j+1) M  ->  M_Config L (K+1) j M
         (shifts one 1 from block 2 into block 1)
         in 5 steps.                          [bump5]

Term5:   M_Config L K 0 M  ->  S_Config L (K+1) M
         (block 2 collapses to size 1; head lands on 0-sep)
         in 5 steps.                          [bump5_term]

Iter:    M_Config L K (j+n) M  ->  M_Config L (K+n) j M
         in 5n steps.                         [bump5_iter]

IterTerm: M_Config L K n M  ->  S_Config L (K+n+1) M
         in 5(n+1) steps.                     [bump5_iter_term]

Finish3: S_Config L K 2  ->  R_Config L K
         (3-step E->B->D->E mini-cycle landing at right blank)
         in 3 steps.                          [finish3_M2]

Full:    M_Config L K n 2  ->  R_Config L (K + n + 1)
         (blocks [..., K, n+2, 2]  ->  [..., K+n+1, 2, 1])
         in 5(n+1) + 3 = 5n + 8 steps.        [macro_to_R]

These rules have been proven in Lean[1].

References