1RB1RA_1LC0RD_1LD1LB_1LE0LF_0RA---_0LB0LE

From BusyBeaverWiki
Jump to navigation Jump to search

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

The tape each time the head reaches a new cell at the left end, for the first 127,000 steps (one row per visit, time running downward).

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).

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.

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

The one difference: state D reading 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.

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

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

  1. 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.
  2. 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