1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD---

From BusyBeaverWiki
Revision as of 10:12, 19 November 2026 by FractalGeometryExplorer (talk | contribs) (Created page with "{{machine|1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD---}} {{TM|1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD---|halt}} (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 10<sup>725</sup> steps (the exact number has not been computed). A machine-checked proof has been submitted to busycoq ([https://github.com/ccz181078/busycoq/pull/108 busycoq pull re...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

The tape each time the head reaches a new cell at the left end, for the first 91,000 steps (one row per visit, time running downward). Each round takes longer than the one before.

How to read the pictures. In both, time runs downward and black cells are 1s. The picture on the right shows every one of the first 600 steps, so you can follow the head (the coloured pixel) as it sweeps back and forth. The picture on the left shows only one row each time the head reaches a new cell at the end of the tape, so it covers a much longer part of the run. Each row there is the whole tape at that moment.

The first 600 steps from a blank tape (time runs downward, black = 1, coloured pixel = head).

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 100 repeated 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.
The layout of the tape (schematic)
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.

One rule table (T4), four starting states
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.

Words used on this page
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:

  1. restates those four rules for T4 and proves them;
  2. redoes every piece of the engine built on them (collisions, returns, defects and the fast right sweep, which needs one extra condition here);
  3. keeps the rest of DeepMind's engine and its correctness proofs unchanged;
  4. 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