1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA

From BusyBeaverWiki
Jump to navigation Jump to search

1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA (bbch) (bbchallenge ID 11019) is a six-state, two-symbol Turing machine from the list of BB(6) holdouts. It does not halt when started on a blank tape. A machine-checked proof was submitted to busycoq in November 2026 (pull request #70) and is awaiting review. A Lean 4 proof is in the busy-beaver-explorer repository.

The machine moves pairs 01 from one long block to another. Every visit to the left end takes 3 pairs from the left block and adds about 6.6 to a bigger block, paced by a short "tail" further right that runs through one of four cycles. When the left block is used up, the big block takes its place, so each round is about 2.1 times longer than the last.

It is the same transition table as 1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC (bbch) started in a different state, and the two proofs share most of their ideas.

Summary

Result Does not halt (proof submitted, under review)
bbchallenge ID 11019
Behaviour Two-block transfer with a tail counter; rounds grow by a factor 2.06 to 2.2
Proof method Closed set of 1,144 classes of round ends (a Collatz-like map that never needs to be solved)
Proofs Rocq (busycoq #70, submitted); Lean 4 (busy-beaver-explorer)

Transition table

0 1
A 1RB 0RD
B 1RC 0LF
C 1LA 0LB
D --- 1RE
E 1LB 1RA
F 0LC 0RA

Renaming the states A→B, B→C, C→A turns the table of 1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC (bbch) into this one. That machine starts in its A, which is this machine's B; this machine starts in A, which is that machine's C. So the two are the same rules started in different states, and their runs are different.

Behaviour

The tape at each visit of the head to the left end, for the first 129,000 steps. The textured triangle on the left is the left block of 01 pairs; the blocks to its right are the big block and the tail.
The first 600 steps from a blank tape (time runs downward, black = 1, coloured pixel = head).

The tape as words

Each time state A arrives at the left end, the tape is

A> 010 (01)a 000 (01)b T

with a left block of a pairs, a big block of b pairs, and a short tail T: small blocks (10)k (k < 70) separated by 000 or 111. For example, at step 9,932,715,748 the tape is

010 (01)2110 0000 (10)56419 000 (10)4 000 (10)13 000 (10)16 000 (10)20 111 0 1

One visit takes 3 pairs from the left block (in five sweeps across the tape) and rewrites the tail.

The tail cycles

The tail is a small finite engine. After a start-up it repeats one of four cycles:

Visits per cycle Left block a Big block b Tail variants
15 −45 +99 3
16 −48 +99 1
22 −66 +141 1
9 −27 +57 1

Rounds

A round ends at a node A> 01001000 (01)B T. Two visits later the left block has B + 3 pairs and a new round starts. The nodes of the actual run have B = 586, 1291, 2827, 6280, 12967, 28531 (step 2,340,515,329), …

The next node depends only on the tail T and on the remainder of B modulo the amount a period of T's cycle eats (45, 48, 66 or 27). This looks like a Collatz-like map, and nobody needs to predict which remainder comes next.

Proof of non-halting

The proof uses a closed set of round ends:

  • A class is a tail T together with a remainder of B (for B ≥ 20000). There are 1,144 classes over 62 tails.
  • For each class, one symbolic run with B left as a free variable plays the whole round and ends at a node. Every remainder that this node's B could have is again a class in the set. No class reaches the halting transition.
  • The actual run enters the set at step 2,340,515,329 (B = 28531, which is 19 mod 66).

So the run stays inside the set forever and never halts. The proof does not need to know which classes are actually visited: all possible remainders are covered.

The exact set matters. Some nearby tails (one block one pair longer or shorter) do halt for every B; for example T = 0000 (10)10 000 (10)4 000 (10)12 111 0000 101 with B = 20002 + 3x halts after 815,565 + 122x steps. So a coarser description such as "any tail" could not be closed.

Related machines

Machine Relation Status
1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC (bbch) (ID 36670) Same table up to renaming the states; started in a different state, so a different run. Does not halt (proof submitted, busycoq #69)
1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA (bbch) (ID 65826) Its proof uses the same symbolic engine (counts of the form c + a·x). Does not halt (proof submitted, busycoq #71)

Proof status

  • Rocq (Coq): submitted to busycoq as pull request #70 (November 2026). Not yet reviewed or merged.
  • Lean 4: theorem nonhalt in holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/lean/Replay.lean of busy-beaver-explorer. Lean's kernel checks the rules and the closed-set argument; 16 long evaluations (one symbolic round per class chunk, the arrival from blank tape and six cycle rules) use native_decide.
  • An interactive explainer is at busy-beaver-explorer's GitHub Pages.

The proofs were written with the help of an AI assistant (Claude) and checked by the proof assistants named above.

References