1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA

From BusyBeaverWiki
Revision as of 04:45, 19 November 2026 by FractalGeometryExplorer (talk | contribs) (Created page with "{{machine|1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA}} {{TM|1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA|non_halt}} (bbchallenge ID '''65826''') 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/71 pull request #71]) and is await...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

For a very long time the run looks irregular: blocks are collected, expanded and drained in phases whose lengths grow about sevenfold. Only after about 1.8 × 1015 steps does it settle into an exact growth cycle: one particular tape shape comes back, every time with a longer final block. Proving that took finding the cycle, which is two "epochs" long and spans about 6.5 × 1017 steps.

Summary

Result Does not halt (proof submitted, under review)
bbchallenge ID 65826
Behaviour Collect / expand / drain phases; exact growth cycle from step 1,818,198,163,340,705
Cycle length 650,373,336,347,246,654 + 4,382,930,856 (r − 65) steps; r grows by 321,042,928 per cycle
Proofs Rocq (busycoq #71, submitted); Lean 4 (busy-beaver-explorer)

Transition table

0 1
A 1RB 0RC
B 0RC 1RC
C 0LD 0RA
D 1LE 0LF
E 0LA 1LC
F --- 1LA

Behaviour

The tape at each visit of the head to the left end, for the first 122,000 steps. The diagonal texture on the left is the block of seven-cell words; the striped region to the right is made of three-cell words 011.
The first 600 steps from a blank tape (time runs downward, black = 1, coloured pixel = head).

The tape as words

Read the tape whenever state E arrives at the left end (an event). The tape is then

  • a left block of seven-cell words (1011001)p,
  • a short irregular zone,
  • blocks of three-cell words (011)n separated by short words such as 0 and 000, ending with a last block (011)r.

Going right, the head shifts a block of three-cell words by one cell (3 steps per word); going left it crosses two words at a time (18 steps). So for what happens at a block's ends, only the parity of the block's length matters.

Three phases

Phase Tape at an event One cycle
Collect 0 (1011001)p (101)5 10 (011)q 000 (011)r, q even, r odd 2 events: p + 2, q − 2
Expand 0 (1011001)p 1011 05 110110011010 (101)m 1000 (011)r, m even 4 events: p − 2, m + 14
Drain 0 (1011001)p 1011 05 1101100110110 (011)16 001101100110 (011)r 72 events: p − 52, r + 414

Collect and expand alternate, so the left block is rebuilt about 7 times longer each time (about 600, 4,370, 30,750, 215,000, 1,506,000 words). Between them come short irregular stretches. Eventually an irregular stretch ends in the drain pattern instead, and the whole left block is poured into the last block: 414 three-cell words for every 52 seven-cell words. The left part then starts again from a small state, in front of a much larger r.

The growth cycle

The left part never looks at r beyond its parity, and drains add even amounts, so r stays odd. After the second drain the left part reaches a state that it comes back to exactly. Define

C(r) = E> 0 (1011001)59 1011 00000 1101100110110 (011)16 001101100110 (011)r

Event Step What happens
2,260,329 6.7 × 1013 First drain: p 1,505,827 → 115, r 4,001 → 11,991,785
5,251,395 1.07 × 1015 Second drain: p 603,155 → 111, r → 16,797,295
6,086,451 1.818 × 1015 C(16,797,709) for the first time
59,675,352 5.4 × 1016 Drain after 11 phases: r → 301,226,589
116,039,645 6.0 × 1017 Drain after 10 phases: r → 337,840,223
122,406,605 7.26 × 1017 C(337,840,637) = C(16,797,709 + 321,042,928)

Proof of non-halting

The key statement is: for every odd r ≥ 65, the configuration C(r) reaches C(r + 321,042,928) after 116,320,154 events. Since 321,042,928 is even, the set {C(r) : r odd, r ≥ 65} is mapped into itself, and it contains no halting configuration. The run from blank tape reaches C(16,797,709), which is in the set.

The cycle is proved by one symbolic run with r = 65 + 2x and x a free variable. The run works on words rather than cells:

  • Shift rules let the head cross any number of copies of a word at once.
  • Counts are numbers or expressions c + a·x. A comparison or division is only done when its answer is the same for every x ≥ 0.
  • Cycle rules (for example "collect" and "expand") are applied many times at once, after checking their precondition.

About 5.6 million such moves cover the whole cycle of about 6.5 × 1017 machine steps.

The exact orbit matters. Nearby configurations halt: the same node with 61 instead of 59 seven-cell words halts after 1,772,276 + 5,220 (r − 65) steps, and C(r) with r even halts too. This is why the regular-language deciders used by bbchallenge cannot settle this machine.

Proof status

  • Rocq (Coq): submitted to busycoq as pull request #71 (November 2026). Not yet reviewed or merged.
  • Lean 4: theorem nonhalt in holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/lean/Replay.lean of busy-beaver-explorer. Lean's kernel proves the symbolic executor sound and proves that the cycle plus the arrival imply non-halting; the two long executor runs (5.6 and 5.0 million moves) and twelve short ones are evaluated with native_decide. Checking takes about one minute.
  • 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.

Related machines

References