1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD---
1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD--- (bbch) (bbchallenge ID 155900) 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 10725 steps (the exact number has not been computed). A machine-checked proof has been submitted to busycoq (busycoq pull request #108). It adapts DeepMind's proof for a table that differs in one transition (busycoq pull request #93, Alex Havrilla).
The head sweeps back and forth over a tape that is rebuilt in rounds, each round bigger than the last. This is what the community calls a bell, and the community tracker files the machine as a "chaotic bell". The tape holds a counter and a list of runs of 1s. In each round the runs pair up and get longer, the counter feeds in new short runs, and the whole tape grows by about 5/4 every two rounds. The details are irregular, so no simple formula predicts the run. The machine halts if one particular four-cell pattern ever appears under the head. Simulations up to 7.9 × 1014 steps never see it. A proof that runs a verified fast simulator shows that it does appear eventually, on a tape about 22410 cells long.
Summary
| Result | Halts (proof submitted, under review) |
|---|---|
| bbchallenge ID | 155900 |
| Steps to halt | more than 10725 (not computed exactly) |
| Tape at the halt | about 22410 cells |
| What it does | A "chaotic bell": rounds of growing size over a counter and a list of runs of 1s |
| Family | The same rule table as three other holdouts, started in a different state (see below) |
| Proofs | Rocq (busycoq #108, under review; adapted from busycoq #93) |
Transition table
| 0 | 1 | |
|---|---|---|
| A | 1RB | 0LC |
| B | 1RC | 1RA |
| C | 1LD | 0RE |
| D | 1LA | 1LD |
| E | 0RA | 0RF |
| F | 0LD | --- |
The machine halts when it is in state F and reads a 1. Following the table backwards: F is entered only from E reading a 1, and E only from C reading a 1. So a halt needs the head, in state B, to see the four cells 0 1 1 1: B reads the 0 and moves right into C, C reads a 1 and moves right into E, E reads a 1 and moves right into F, and F reads the last 1. The question "does it halt?" is the same as "does B ever meet 0 1 1 1?"
Behaviour
Reading the tape
Look at the tape just after the head has swept to the right. It has two kinds of pieces:
- the counter: the three-cell word
100repeated many times. Its size is the number of copies. - runs of 1s, separated by
00. Almost every run has length 7, 13, 19, 25, … (each 6 longer than the last). Runs of the same length stand together in a group: first all the 7s, then all the 13s, and so on. A few odd runs sit between the groups.
| Piece | counter | group of 7s | group of 13s | group of 19s | … |
|---|---|---|---|---|---|
| On the tape | 100 100 100 … |
7 ones, 00, 7 ones, 00, … |
13 ones, 00, 13 ones, … |
19 ones, 00, … |
… |
Rounds
The run goes in rounds (epochs). In each round:
- each group of runs is halved, and the runs that remain move up one length (7 → 13 → 19 → …);
- half of the counter is turned into new runs of length 7;
- a new counter is built, about 5/2 times as long as the old number of 7s.
So the tape grows by a factor of about 5/4 every two rounds, and the number of steps per round grows by about (5/4)2 = 25/16. This growth is what makes the machine a bell.
The halving is not exact. Sometimes a group loses one run more or less, and the odd runs between the groups change from round to round with no visible rule. Those small irregularities make this a chaotic bell: the overall shape is predictable, but whether the halting pattern turns up in any particular round is not. An exact fast simulation finds no halt in the first 7.9 × 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, the renamed table behaves like the original started in some other state. Renaming the states shows that this machine and two other holdouts are a single table, called T4 here, written as 1RB1RA_1LC0RD_1LD1LB_1RA0LE_0LB0LF_0RA---. Some of the renamings also swap left and right. The machines differ only in the state they start in. A fourth holdout is a slowed-down copy of T4 started in A.
| 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 | this machine (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 |
|---|---|
| Counter | A long stretch of the word 100 repeated.
|
| Run | A stretch of 1s between two 00s; lengths are 7, 13, 19, ….
|
| Group | All the runs of one length, standing together. |
| Round (epoch) | One cycle in which the groups halve and move up, and the counter is rebuilt. |
| Bell | A machine whose run is a sequence of sweeps over a tape that grows round after round. |
| T4 | The rule table shared by this machine and three other holdouts. |
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.
DeepMind wrote such an engine for the neighbouring table. It works with words such as 1 (11)n 00, read as a digit n. Only four of its basic rules use the one transition where T4 differs (F reading a 0). For T4 each of these ends in a slightly different place, which moves a carry from one digit to the next. The proof:
- restates those four rules for T4 and proves them;
- redoes every piece of the engine built on them (collisions, returns, defects and the fast right sweep, which needs one extra condition here);
- keeps the rest of DeepMind's engine and its correctness proofs unchanged;
- runs the proved engine from a blank tape. After 261,156 engine steps it reaches the head in state F reading a 1, with about 22410 cells on the tape.
Since the head must have visited every one of those cells, the machine ran for more than 22410 ≈ 10725 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 33 minutes with the VM, nearly all of it the final run.
The same engine, started in states C and D, also reaches a halt (after 427,055 and 688,228 engine steps), which covers the two other machines in the table above.
Proof status
- Rocq (Coq): a single file,
verify/M_1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LDHHH.v, submitted to busycoq in pull request #108; not yet reviewed or merged. It is DeepMind's file from pull request #93, changed as described above. - An interactive explainer is at busy-beaver-explorer's GitHub Pages.
The adaptation was done 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 (the Rocq file, its generator and the engine runs)

