1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---

From BusyBeaverWiki
Jump to navigation Jump to search

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

The tape each time the head reaches a new cell at the left end, for the first 109,000 steps (one row per visit, time running downward). The tape grows to the left. 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 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 110 repeated many times;
  • groups: the word 10 repeated 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:

The start of the tape at step 1,656
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.

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

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

  1. 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).
  2. 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.
  3. 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.v in 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