1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---
1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC--- (bbch) (bbchallenge ID 127983) 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 101312 steps (the exact number has not been computed). A halting proof has been submitted to busycoq by valu42 (busycoq pull request #100) and is under review. An independent Rocq proof, adapted from DeepMind's proof for a table that differs in one transition (busycoq pull request #93, Alex Havrilla), is in the busy-beaver-explorer repository.
The tape grows to the left, and the head keeps coming back to the left end. Right next to the left end sits a growing stack of the word 110, which gets two copies longer on each visit. Behind it lies a list of groups of the word 10. As the head sweeps back and forth, it merges these groups into bigger ones of sizes 4, 7, 10, 13, …. When the list has been used up far enough, the stack of 110s is broken up into new small groups and a new, larger round begins. This is a bell: rounds of growing size with irregular details, so no simple formula predicts the run. The machine is the same rule table as three other holdouts, started in a different state, and a proof that runs a verified fast simulator shows that it halts on a tape about 24360 cells long.
Summary
| Result | Halts (proof submitted, under review) |
|---|---|
| bbchallenge ID | 127983 |
| Steps to halt | more than 101312 (not computed exactly) |
| Tape at the halt | about 24360 cells |
| What it does | A bell: a stack of 110s and a list of groups of 10s, rebuilt in rounds of growing size
|
| Family | The same rule table as three other holdouts, started in a different state (see below) |
| Proofs | Rocq (busycoq #100 by valu42, under review); an independent Rocq proof in busy-beaver-explorer, adapted from busycoq #93 |
Transition table
| 0 | 1 | |
|---|---|---|
| A | 1RB | 1RD |
| B | 1LC | 0RE |
| C | 1LD | 1LC |
| D | 1RA | 0LB |
| E | 0RD | 0RF |
| F | 0LC | --- |
The machine halts when it is in state F and reads a 1. State F is entered only from state E reading a 1 (0RF). So a halt needs the head, in state E, to see two 1s in a row.
Behaviour
Reading the tape
Look at the tape each time the head reaches the left end in state B. Reading from left to right, it always has the same layout:
- two blank cells,
00, where the head is; - the stack: the word
110repeated many times; - groups: the word
10repeated some number of times. The number of copies is the group's size. - Between two groups there is a single separator
1.
For example, at step 1,656 the tape begins like this:
| Piece | head here | stack | group | separator | group | separator | group | separator | group | … |
|---|---|---|---|---|---|---|---|---|---|---|
| On the tape | 00 |
110 110 110 |
10 10 |
1 |
10 10 10 |
1 |
10 10 10 10 |
1 |
10 10 |
… |
| Size | 3 copies | 2 | 3 | 4 | 2 |
So the whole tape can be described by two things: how tall the stack is, and the list of group sizes.
Rounds
The run goes in rounds. During a round:
- every visit to the left end makes the stack two copies taller;
- the sweeps of the head merge neighbouring groups, so that the list settles into long runs of groups of equal size, with sizes 4, 7, 10, 13, … (each 3 larger than the last).
When the list has been used up far enough, the round ends with a reset: the stack is broken up into about half as many groups of size 4 as it had copies of 110, and a new round starts with a short stack. Large and small resets alternate, and each round is bigger than the one before.
How many groups there are of each size behaves a little like the digits of a counter with several levels: groups of size 4 combine into groups of size 7, those into groups of size 10, and so on. The exact rule for these "carries" has not been worked out, and the proof does not need it. An accelerated simulation finds no halt in the first 1.48 × 1014 steps.
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. Rename this machine's states (A→C, B→D, C→A, D→B) and exchange left and right, and it becomes the table 1RB1RA_1LC0RD_1LD1LB_1RA0LE_0LB0LF_0RA---, called T4 here, started in state C. T4 started in states B and D gives two more holdouts, and T4 started in A is not itself on the holdout list, but a slowed-down copy of it is.
| Start T4 in | Holdout | How it relates to T4 | Status |
|---|---|---|---|
| A | 1RB1RA_1LC0RD_1LD1LB_1LE0LF_0RA---_0LB0LE (bbch) (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 | this machine (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 |
|---|---|
| Stack | The word 110 repeated many times, right next to the left end of the tape.
|
| Group | The word 10 repeated some number of times (its size).
|
| Separator | The single 1 between two groups.
|
| Round | The time between two resets. |
| Reset | The end of a round, when the stack is broken up into new groups of size 4. |
| T4 | The rule table that this machine is, after renaming and mirroring, started in state C. |
Proof of halting
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. The engine is DeepMind's from busycoq pull request #93. T4 differs from DeepMind's table in one transition (state F reading a 0). Four of the engine's basic rules use that transition, so they are restated for T4 and everything built on them is redone. This is the same engine used for
1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD---(bbch). - The start. This machine is T4 renamed and mirrored, so the proof for
1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD---(bbch) carries over with the rule table, the renaming of the states and the starting state changed. - The run. From state C, the engine reaches the halting configuration (the head in state F on a 1) after 427,055 engine steps, when the tape holds about 24360 cells.
The head has to visit every cell of a tape about 24360 ≈ 101312 cells long, so the run takes more than 101312 steps.
The theorem is halt : halts tm c0 on busycoq's definitions. Print Assumptions halt reports no axioms. Rocq 8.18 checks the file in about 4 hours with the VM, and nearly all of that time is the final run.
Proof status
- Rocq (Coq): valu42 submitted a halting proof to busycoq in pull request #100. The independent proof is
holdouts/1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---/coq/H127983.vin busy-beaver-explorer. It was not submitted. - An interactive explainer is at busy-beaver-explorer's GitHub Pages.
The independent proof was adapted with the help of an AI assistant (Claude) and checked by Rocq as described above.
References
- busycoq pull request #100 (valu42's proof for this machine)
- busycoq pull request #93 (DeepMind's proof for the neighbouring table)
- Machine folder in busy-beaver-explorer

