1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB

From BusyBeaverWiki
Revision as of 04:35, 19 November 2026 by FractalGeometryExplorer (talk | contribs) (Created page with "{{machine|1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB}} {{TM|1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB|non_halt}} (bbchallenge ID '''113677''') 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. This is proved in Lean 4 in the [https://github.com/fractal-geometry-explorer/busy-beaver-explorer busy-beaver-explorer] repository (November 2026). The proof has not yet been submit...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB (bbch) (bbchallenge ID 113677) 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. This is proved in Lean 4 in the busy-beaver-explorer repository (November 2026). The proof has not yet been submitted to busycoq or reviewed by others.

The tape grows on both sides, roughly like the square root of the number of steps. The run alternates between round-trip phases, in which the head bounces between the two ends while a few counts change by fixed amounts, and right phases, in which it works only near the right end. Ten tape shapes and twenty transitions between them describe the whole run, and a set of linear inequalities shows that the run can never leave them.

Summary

Result Does not halt (Lean proof; not yet independently reviewed)
bbchallenge ID 113677
Behaviour Alternating round-trip and right phases over ten tape forms; two-sided square-root growth
Proof method Branch table of proved rules + invariant made of linear inequalities (found by linear programming)
Proofs Lean 4 (busy-beaver-explorer)

Transition table

0 1
A 1RB 0LE
B 1RC ---
C 1RD 1RE
D 1LA 0RF
E 0RC 0LA
F 0LC 0RB

The only halting transition is B reading a 1. B is entered from A reading a 0 and from F reading a 1, so the machine halts exactly when it meets A> 0 1 or F> 1 1.

Behaviour

The tape at each visit of the head to the left end, for the first 119,000 steps. The textured region on the left holds the runs of 1000 and 10; the sparse vertical stripes on the right are the 14-cell words.
The first 600 steps from a blank tape (time runs downward, black = 1, coloured pixel = head).

Round-trip phases

At the visits to the left end during a round-trip phase the tape looks like

0∞ A> 07 (1000)a (10)b (00001000001000)c 101

three counts a, b, c written as runs of a 4-cell word, a 2-cell word and a 14-cell word. The visits run through an exact cycle of four shapes, after which (a, b, c) has become (a + 3, b + 12, c − 2). For example:

Step a b c
824,136 80 219 59
847,516 83 231 57
1.044 × 1011 30,424 87,941 19,564

So the 14-cell words are used up two at a time while the other two runs grow.

Right phases

When the 14-cell words run out (c = 0 or 1), the head stops returning to the left end. At its visits to the right end the tape looks like

0∞ (1110)a (1111110)k 111 001 (10)m 1 E> 0∞

and every visit turns one 10 into one 1111110 (m − 1, k + 1). When one 10 is left, pairs of 1111110 are folded into new 14-cell words and the next round-trip phase begins.

Ten forms

Odd and even round-trip phases differ, and leftover words can leave a third run frozen in place, so the full description uses ten tape forms (named O, S1, RF, EF, T3, T2, U3, RG, RG3 and O with b = 0). Each form has a cycle and an exit, depending on a remainder (c mod 2, a count mod 5, or a parity). That gives 20 cases, and each case changes the counts by an affine map.

Phase boundaries along the actual run
Step Phase that starts
29,301 odd round trip
191,775 even round trip
808,896 odd round trip
6,370,604 even round trip
27,629,379 odd round trip
223,234,215 even round trip
735,331,316 right phase (three runs of 10)
976,078,402 two-run round trip
3,043,404,308 odd round trip
7,125,828,416 right phase
22,249,365,380 even round trip

Proof of non-halting

  1. Rules. Every move in the branch table (cycles, their k-fold repetitions, exits and re-pairings) is a Lean theorem for all values of its counts, with an exact step count.
  2. Start. From blank tape the machine reaches the first form O 14 37 11 at step 29,301, and the table carries it on for 196 more moves (to step about 5.7 × 1029).
  3. Invariant. A predicate Good is a list of linear inequalities for each form (3 to 16 per form). It says that the growing counts keep their ratios inside a cone, that the bounded counts stay in range, and that a size measure is large enough. Every one of the 20 cases maps a Good configuration to a Good one after at least one step.
  4. The end of step 2 is Good, so the run continues forever and never halts.

The inequalities were found by linear programming over the replayed run; the proof only checks them.

Proof status

  • Lean 4: theorem nonhalting in holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/lean/Closed.lean of busy-beaver-explorer, checked by Lean's kernel alone (no native_decide).
  • Coq / busycoq: not submitted yet.
  • An interactive explainer is at busy-beaver-explorer's GitHub Pages.

The proof was written with the help of an AI assistant (Claude) and checked by Lean.

References