1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC
1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC (bbch) (bbchallenge ID 36670) 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 of this was submitted to busycoq in November 2026 (pull request #69) and is still awaiting review. An independent proof in Lean 4 is in the busy-beaver-explorer repository.
The machine keeps a list of numbers on its tape, written as long stretches of the word 01. It sweeps back and forth, taking 3 from the first number and adding to a later one, in one of four repeating patterns. When the first number runs out, the next one takes its place and is roughly twice as big, so the machine is always busy and never reaches its halting transition.
It is the same machine as 1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA (bbch) started in a different state (see below).
Summary
| Result | Does not halt (proof submitted, under review) |
|---|---|
| bbchallenge ID | 36670 |
| Behaviour | Counter list in 01 blocks; four periodic regimes; epochs that roughly double
|
| First epoch sizes | 4, 12, 20, 38, 68, 122, 240, 484, 1002, 2104, 4375, … |
| Proofs | Rocq (busycoq #69, submitted); Lean 4 (busy-beaver-explorer) |
Transition table
| 0 | 1 | |
|---|---|---|
| A | 1RB | 0LF |
| B | 1LC | 0LA |
| C | 1RA | 0RD |
| D | --- | 1RE |
| E | 1LA | 1RC |
| F | 0LB | 0RC |
The only halting transition is D reading a 0. State D is entered only from C reading a 1 (0RD), so a halt needs the head, in state C, to see 1 0. In the actual run C always sees 1 1 there.
Behaviour

01 stretches; the left one shrinks while the ones to its right grow.
The tape as a list of numbers
Look at the tape each time state B arrives at the left end. It then reads
B> 00 (01)a 000 (01)b 000 …
that is, a list of numbers a, b, … written as stretches of 01, separated by short words such as 000. (Here (01)a means the word 01 repeated a times, and B> marks the head in state B.)
The head moves across these stretches in long sweeps. Going right it rewrites each 010101 as 011001 (14 steps per copy); going left it turns them back (22 steps per copy). So a sweep across a stretch leaves it unchanged in size, and only the short words between the stretches really change.
Round trips, regimes and epochs
- Round trip. Each trip of the head to the far end and back takes 3 off the first number a.
- Regimes. Meanwhile, the rest of the list cycles through one of four periodic patterns, called R0 to R3 below, with periods of 15, 22, 16 and 9 round trips. Over one period the second number b grows by 99, 141, 99 or 57.
- Epochs. When a is used up (a = 4) the left end is rebuilt, and b (plus a constant) becomes the new first number. After a transient of up to about 150 round trips the list settles into one of the four regimes again.
| Regime | Period (round trips) | a per period | b per period |
|---|---|---|---|
| R0 | 15 | −45 | +99 |
| R1 | 22 | −66 | +141 |
| R2 | 16 | −48 | +99 |
| R3 | 9 | −27 | +57 |
Because b grows by about 2.1 to 2.2 for every 1 taken from a, each epoch is about twice as long as the previous one. The first numbers at the starts of the epochs are 4, 12, 20, 38, 68, 122, 240, 484, 1002, 2104, 4375, …
Proof of non-halting
The proof follows the description above. In outline:
- Shift rules. The two sweeps (
010101↔011001) are proved once for any number of copies. - 62 templates. The four regimes together have 15 + 22 + 16 + 9 = 62 phases. Each phase is a template
B> 00 (01)3k+4 000 (01)3j+β …with two free counts k and j. For each template, a symbolic run shows that it leads to the next template with k one smaller and j larger, for every value of k and j. - Epoch ends. For each template, a symbolic run also handles the case k = 0 (the first number is used up) and shows where the next epoch starts, again for all large enough j.
- Start. From the blank tape, the machine reaches one of the templates (regime R1, with a = 118 and b = 496) at step 1,277,431.
- Closing the loop. A simple potential (j + 2k + a constant per template) never decreases, so the size condition needed in step 3 always holds. The run therefore goes through the templates forever and never halts.
The symbolic runs are carried out by a checker whose soundness is itself proved, so a wrong number anywhere makes the proof fail rather than giving a false result.
Related machines
| Machine | Relation | Status |
|---|---|---|
1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA (bbch) (ID 11019)
|
Same transition table up to renaming the states (A→B, B→C, C→A); that machine is this table started in state C. The two runs are different: no configuration of one appears in the other in the first 107 steps. | Does not halt (proof submitted, busycoq #70) |
Proof status
- Rocq (Coq): submitted to busycoq as pull request #69 (November 2026). Not yet reviewed or merged.
- Lean 4: theorem
H36670.nonhaltinginholdouts/1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC/lean/Cert.leanof busy-beaver-explorer. The rules and the 62 round trips are checked by Lean's kernel; the start and the 62 epoch ends usenative_decide. Checking takes about 5 minutes on one core. - 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
- Machine folder in busy-beaver-explorer (Lean proof, notes and simulators)