1RB1RA_1LC0RD_1LD1LB_1LE0LF_0RA---_0LB0LE
1RB1RA_1LC0RD_1LD1LB_1LE0LF_0RA---_0LB0LE (bbch) (bbchallenge ID 181655) is a six-state, two-symbol Turing machine from the list of BB(6) holdouts. Started on a blank tape, it halts, after more than 101072 steps (the exact number has not been computed). A machine-checked proof has been submitted to busycoq (busycoq pull request #109). It builds on DeepMind's proof for a neighbouring table (busycoq pull request #93, Alex Havrilla).
This machine is a slowed-down copy of another rule table, called T4 here. Wherever T4 takes one particular step, this machine takes a three-step detour that ends in the same place, and everywhere else the two behave identically. A detour can also end in a halt if it meets a 1. So this machine does whatever T4 does, only more slowly, and it may stop sooner but never later. T4, started in state A, is a "chaotic bell": a tape rebuilt in rounds of growing size, with irregular details. T4 is proved to halt from state A, on a tape about 23562 cells long, so this machine halts too.
Summary
| Result | Halts (proof submitted, under review) |
|---|---|
| bbchallenge ID | 181655 |
| Steps to halt | more than 101072 (not computed exactly) |
| What it does | A slowed-down copy of the table T4 started in state A; a "chaotic bell" of blocks of 1s whose counts halve each round |
| Family | T4 started in states B, C and D gives three other holdouts (see below) |
| Proofs | Rocq (busycoq #109, under review; builds on busycoq #93) |
Transition table
| 0 | 1 | |
|---|---|---|
| A | 1RB | 1RA |
| B | 1LC | 0RD |
| C | 1LD | 1LB |
| D | 1LE | 0LF |
| E | 0RA | --- |
| F | 0LB | 0LE |
The machine halts when it is in state E and reads a 1. State E is entered from D reading a 0 (1LE) and from F reading a 1 (0LE).
Behaviour
Rounds of blocks
Look at the tape each time the head reaches the left end in state E. It is a list of blocks of 1s separated by 00. Almost every block has length 1, 7, 13, 19, … (each 6 longer than the last), and blocks of the same length stand together in a group, with a few irregular blocks between the groups.
| Piece | group of 19s | group of 13s | group of 7s | group of 1s |
|---|---|---|---|---|
| On the tape | 19 ones, 00, … |
13 ones, 00, … |
7 ones, 00, 7 ones, … |
1 00 1 00 1 00 …
|
From one round to the next, the blocks of every group pair up, and each pair becomes one block six cells longer. So the number of 13s in a round is about half the number of 7s in the round before, and so on up the list. Each round also adds a new group of blocks of length 1 on the right. Like a binary counter, the long blocks are rare and the tape grows round after round. An accelerated simulation finds no halt in the first 6.6 × 1014 steps.
A slowed-down copy
Swap the names of states E and F. The table becomes 1RB1RA_1LC0RD_1LD1LB_1LF0LE_0LB0LF_0RA---. This differs from T4 = 1RB1RA_1LC0RD_1LD1LB_1RA0LE_0LB0LF_0RA--- in a single entry: what state D does when it reads a 0.
| T4 | This machine (E and F swapped) | |
|---|---|---|
| Steps | 1 | 3, or a halt |
| What happens | Write 1, move right, go to A. | Write 1, move left into the next state. If that cell is 0: write 0, move back right into A, read the 1 just written, and (A reading 1 = 1RA) move right in A. This ends exactly where T4's single step ends.If that cell is 1: halt. |
So this machine follows T4's run from state A step for step, except that each "D reads 0" step becomes a three-step detour, unless one of the detours halts first.
One table, four starts
A Turing machine always starts in state A. If you rename the states of a table, you get a table that looks different but does the same thing; started in A, it behaves like the original started in another state. T4 started in states B, C and D is, after renaming (and for one of them mirroring), exactly three other holdouts. T4 started in A is not itself on the holdout list, but this machine is its slowed-down copy.
| Start T4 in | Holdout | How it relates to T4 | Status |
|---|---|---|---|
| A | this machine (ID 181655) | a slowed-down copy (see the article) | Halts; proof submitted (busycoq #109) |
| B | 1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD--- (bbch) (ID 155900) |
renamed | Halts; proof submitted (busycoq #108) |
| C | 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC--- (bbch) (ID 127983) |
renamed and mirrored | Halts; proof submitted by valu42 (busycoq #100) |
| D | 1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB--- (bbch) |
renamed | Halts; proof submitted to busycoq by others |
T4 is itself one transition away from another table, 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0RD--- (bbch) (after the same renaming). DeepMind proved that machine halts, in busycoq pull request #93 (Alex Havrilla). The proofs for this family reuse that proof.
| Word | Meaning |
|---|---|
| Block | A stretch of 1s between two 00s; lengths are 1, 7, 13, 19, ….
|
| Group | All the blocks of one length, standing together. |
| Round | From one arrival of the head at the left end in state E to the next. |
| T4 | The rule table of which this machine is a slowed-down copy. |
| Detour | The three steps this machine takes where T4 takes one. |
Proof of halting
- The detour lemma. For every configuration and every number of steps: if T4 halts from a configuration, then this machine (with E and F swapped) halts from the same configuration. The proof is an induction on T4's steps. Every transition except "D reads 0" is identical, and that one is either the three-step detour or a halt.
- T4 halts from state A. The machine runs far too long to simulate cell by cell, so the proof uses a fast engine: a program that treats the tape as a list of repeated words and jumps over whole blocks at once. Every kind of jump it makes is proved, once and for all, to give exactly what the machine would do. Running the engine until it reaches a halting configuration is then a proof that the machine halts, and Rocq's kernel checks that run. The engine is DeepMind's from busycoq pull request #93, changed in the four rules that use the one transition where T4 differs from DeepMind's table, and in everything built on them. This is the same engine used for
1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD---(bbch), started in A instead of B. From state A it reaches T4's halting configuration (F reading a 1) after 350,227 engine steps, on a tape of about 23562 cells.
Together these show that this machine halts. The head has to visit every cell of a tape about 23562 ≈ 101072 cells long, so the run takes more than 101072 steps. The proof does not say whether the machine stops at T4's halt or earlier, at a detour that meets a 1.
The theorem is halt : halts tm c0 on busycoq's definitions. Print Assumptions halt reports no axioms.
Proof status
- Rocq (Coq): a single file,
verify/M_1RB1RA_1LC0RD_1LD1LB_1LE0LF_0RAHHH_0LB0LE.v, submitted to busycoq in pull request #109; not yet reviewed or merged. Rocq 8.18 checks it in 45 minutes or more with the VM, nearly all of it the final run. - 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 Rocq as described above.
References
- busycoq pull request #93 (DeepMind's proof for the neighbouring table)
- Machine folder in busy-beaver-explorer

