1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA0RE_1RE---

From BusyBeaverWiki
Revision as of 05:31, 19 November 2026 by FractalGeometryExplorer (talk | contribs) (Created page with "{{machine|1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA0RE_1RE---}} {{TM|1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA0RE_1RE---|halt}} (bbchallenge ID '''32161''') is a six-state, two-symbol Turing machine from the list of BB(6) holdouts. It '''halts''' when started on a blank tape, after roughly 10<sup>24266</sup> to 10<sup>24267</sup> steps (a number with about 24,267 digits). A machine-checked proof was submitted to [https://github.com/ccz181078/busycoq busycoq] in Novemb...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA0RE_1RE--- (bbch) (bbchallenge ID 32161) is a six-state, two-symbol Turing machine from the list of BB(6) holdouts. It halts when started on a blank tape, after roughly 1024266 to 1024267 steps (a number with about 24,267 digits). A machine-checked proof was submitted to busycoq in November 2026 (pull request #72) and is awaiting review. A Lean 4 proof is in the busy-beaver-explorer repository.

The machine behaves like two binary counters ticking together, one on each side of a small "engine" in the middle of the tape. Underneath, each pass of the head rewrites a stream of short words by a handful of simple rules. One word, 1011, makes it halt. Following the rules shows that this word first appears in round 161,211.

It has a twin, 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE--- (bbch), which differs in one transition and halts in the same round.

Summary

Result Halts (proof submitted, under review)
bbchallenge ID 32161
Steps to halt between 6.3 × 1024266 and 1.08 × 1024267 (computed, not proved)
Halting round 161,211
Behaviour Two binary counters around an engine; a word-rewriting "visit law"
Proofs Rocq (busycoq #72, submitted); Lean 4 (busy-beaver-explorer)

Transition table

0 1
A 1RB 0LB
B 0RC 0LE
C 1RD 0RF
D 1LB 1RB
E 0LA 0RE
F 1RE ---

The highlighted cell (E reading 1) is the only difference from the twin machine, which has 1RB there. The machine halts in F reading a 1; F is entered only from C reading a 1.

Behaviour

The tape at each visit of the head to the left end, for the first 109 steps (three pixels per cell). The tape is only about 250 cells wide: the counters grow exponentially slowly. The binary-counter pattern on the right is clearly visible.
The first 600 steps from a blank tape (time runs downward, black = 1, coloured pixel = head).

Two counters

Most of the time the tape looks like L · engine · R. Each time the head passes the engine, it adds 1 to two binary counters, one on each side:

  • Left side: clockwork. When the left counter overflows, the carry reaches the left end, the tape grows by two cells and the counter restarts. The busiest cell turns over 3 · 2k times between consecutive extensions of the left end, each count twice: 48, 96, 96, 192, 192, …
  • Right side. The right counter's digits are spread out, with some fixed stretches ("junk") between them that carries have to cross.

Because the tape grows only when a counter overflows, the run is very long while the tape stays small: about 250 cells after 109 steps, and the word the checker tracks has only about a million cells at the halt.

The visit law

A cleaner way to see the run is through visits. In a visit, the head stands on a 0 with another 0 on its left and a stream s of cells on its right. It runs into the stream, comes back two cells further left, and leaves the stream rewritten as v(s). What happens depends only on how s begins:

Stream begins with After the visit Cost in steps
0 s 1 s 4 or 8
100 s 000 v(s) 6
110 s 000 v(s) 8
1010 s 1010 v(v(s)) 20
1011 s the machine halts –

In this machine the visits come in two forms (the head arriving in state C or in state F). The second form follows the same rules except for 110, so the 1010 rule only holds when the stream behind does not start with 11. Lean proves that this restriction never matters after the first two visits to a stream, and the checker tests it wherever it applies the rule.

The rules call themselves: a visit to 100 s includes a visit to s, and a visit to 1010 s includes two. So 000 and 100 act as binary digits that pass every second visit on, and the whole stream behaves like a nested binary counter: about 2r/2 visits pass through the stream in round r. This is the same rewriting system as in problem 10 of the Beaver Math Olympiad.

The run from blank tape is a sequence of rounds. After 6 steps the tape is 0∞ A> 1 0 0 S1 with S1 = 1 0∞, and each round turns 0∞ A> 1 0 0 S into 0∞ A> 1 0 0 v(1 0 S).

Proof of halting

  1. The visit law (the table above) is proved for every stream and every tape to its left.
  2. An abstract version of the law, with no machine in it, is a small rewriting system on words. Lean proves that the machine follows it.
  3. A checker runs the rewriting system round by round. It keeps the number of pending visits as a pair (e, c) meaning 2e − c, so even astronomically many visits cost one step per cell of the word. The checker's correctness is proved.
  4. The run. The checker shows that rounds 1 to 161,210 use only the four rewriting rules, and round 161,211 meets 1011, so the machine halts. The last word has 1,001,253 cells. In Lean the evaluation is cut into ten segments (about 3 hours of computing in all); in Rocq it is a single vm_compute of about 15 minutes.

How many steps

Every kind of visit costs a fixed number of steps apart from its nested visits, so the total is a weighted count of visits. Summing over all 161,210 rounds gives between 6.3 × 1024266 and 1.08 × 1024267 steps (190.3 · 280605 to 323.1 · 280605). This number is computed, not part of the proof.

Related machines

Machine Relation Status
1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE--- (bbch) (ID 60498) Twin: E reading 1 is 1RB instead of 0RE. Same visit law and same halting round. Halts (proof submitted, busycoq #73)
1RB0LB_0RC0LD_1LD1RE_0LA0RF_0RD1RF_0RC--- (bbch) and two relatives Obey the same law with one form of visit; shown to halt in round 161,211 in busycoq PR #59 (also under review), independently of this proof. Halts (proof submitted)

Proof status

  • Rocq (Coq): submitted to busycoq as pull request #72 (November 2026). Not yet reviewed or merged.
  • Lean 4: theorem halts_from_blank in holdouts/1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA0RE_1RE---/lean/Halt.lean of busy-beaver-explorer. Everything is checked by the kernel except the evaluation of the verified checker, which uses native_decide.
  • An interactive explainer is at busy-beaver-explorer's GitHub Pages.

The proofs were written with the help of an AI assistant (Claude) and checked by the proof assistants named above.

References