1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---

From BusyBeaverWiki
Revision as of 04:49, 19 November 2026 by FractalGeometryExplorer (talk | contribs) (Created page with "{{machine|1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---}} {{TM|1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---|non_halt}} (bbchallenge ID '''32641''') 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 [https://github.com/ccz181078/busycoq busycoq] in November 2026 ([https://github.com/ccz181078/busycoq/pull/74 pull request #74]) and is await...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC--- (bbch) (bbchallenge ID 32641) 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 #74) and is awaiting review. A Lean 4 proof is in the busy-beaver-explorer repository.

The machine goes through five irregular "epochs", each about 3.7 times longer than the last. Then, at step 16,730,681,219, it becomes an exact bouncer: a row of identical 13-cell blocks grows by one block per period, next to a fixed stretch of 222,182 cells that the head visits on every period but always leaves as it found it.

Summary

Result Does not halt (proof submitted, under review)
bbchallenge ID 32641
Behaviour Five irregular epochs, then a bouncer with a fixed far end
Bouncer reached at step 16,730,681,219
Period 184n + 3,029,224 steps; one 13-cell block added per period
Proofs Rocq (busycoq #74, submitted); Lean 4 (busy-beaver-explorer)

Transition table

0 1
A 1RB 0RC
B 1LA 0LD
C 1RB 0RD
D 1LE 0RF
E 0LB 0RB
F 1RC ---

The only halting transition is F reading a 1, and F is entered only from D reading a 1, so a halt needs D> 1 1.

Behaviour

The tape at each visit of the head to the right end, for the first 111,000 steps. The left edge moves in steps as the turning point of the leftward sweeps runs back to it; this is the first of the irregular epochs.
The first 600 steps from a blank tape (time runs downward, black = 1, coloured pixel = head).

Before the bouncer

The head sweeps back and forth. The leftward sweeps turn at a point that drifts right by about 7 cells per sweep, while the right end grows by about 4.5 cells per sweep. When the turning point catches up with the right end, it runs back to the left end and an epoch is over. This happens five times:

Epoch Turning point meets the right end (sweep) Right end then at cell Returns to the left end (sweep)
1 150 774 250
2 650 3,024 950
3 2,550 11,648 3,600
4 9,500 42,923 13,350
5 35,550 160,189 49,300

This part of the description is an observation, not part of the proof. The proof does not need it: it simply checks the first 16.7 billion steps.

The bouncer

After the fifth return (step 16,730,681,219) the tape is exactly

C(k) = 0∞ A> 0 (1010001000100)k X 0∞

with k = 7. Here 1010001000100 is a 13-cell block and X is a fixed stretch of 222,182 cells: the record left behind by the five epochs.

One period takes C(n + 1) to C(n + 2) in 184n + 3,029,224 steps:

Piece What happens Steps
Sweep 1 The head runs right over the blocks, rewriting each one 37n + 38
Excursion 1 The head works inside X and comes back 1,517,479
Sweep 2 Left to the end and right again 92n + 99
Excursion 2 A second visit to X 1,511,551
Sweep 3 Back to the left end, rewriting the blocks again 55n + 57

The two excursions never move left of the one to three cells written next to X, so they are the same in every period. Together they leave X as it was, with one more 13-cell block in front of it, and a rotation identity (1 0 (1000100010010)n = (1010001000100)n 1 0) shows that the rewritten blocks are the original ones again. Per period the tape grows by one block.

Proof of non-halting

  1. The period is proved for every n. The three sweeps are shift rules proved by induction on the number of blocks; the two excursions are finite computations (about 1.5 million steps each) on a window of the tape, and a run inside a window is valid whatever lies outside it.
  2. The arrival. The run from blank tape reaches C(7) at step 16,730,681,219. In Lean this is checked with a block simulator (16-cell blocks, proved correct) in eight chunks; in Rocq with a 32-cell block simulator whose look-up table is checked against direct simulation.
  3. Since C(7) is reached and every C(k) leads to C(k + 1), the machine never halts.

Proof status

  • Rocq (Coq): submitted to busycoq as pull request #74 (November 2026), one self-contained file. Not yet reviewed or merged.
  • Lean 4: theorem nonhalting in holdouts/1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---/lean/Reach.lean of busy-beaver-explorer. The kernel checks the sweeps and the block simulator; the excursions, the block table and the eight chunks of the run use native_decide (about 25 minutes in all).
  • An informal proof with the same argument was posted on the bbchallenge Discord in November 2026.
  • 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