1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB
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

1000 and 10; the sparse vertical stripes on the right are the 14-cell words.
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.
| 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
- 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.
- Start. From blank tape the machine reaches the first form
O 14 37 11at step 29,301, and the table carries it on for 196 more moves (to step about 5.7 × 1029). - 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.
- 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
nonhaltinginholdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/lean/Closed.leanof busy-beaver-explorer, checked by Lean's kernel alone (nonative_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
- Machine folder in busy-beaver-explorer (Lean proof, replay, notes)