1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE

From BusyBeaverWiki
Revision as of 05:25, 19 November 2026 by FractalGeometryExplorer (talk | contribs) (Created page with "{{machine|1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE}} {{TM|1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE|halt}} (bbchallenge ID '''172044''') is a six-state, two-symbol Turing machine from the list of BB(6) holdouts. It '''halts''' when started on a blank tape, after about '''8.53 × 10<sup>131</sup>''' steps, at the left end of a tape about 2.9 × 10<sup>66</sup> cells long. A machine-checked proof was submitted to [https://github.com/ccz181078/busyco...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE (bbch) (bbchallenge ID 172044) is a six-state, two-symbol Turing machine from the list of BB(6) holdouts. It halts when started on a blank tape, after about 8.53 × 10131 steps, at the left end of a tape about 2.9 × 1066 cells long. A machine-checked proof was submitted to busycoq in November 2026 (pull request #76) and is awaiting review. A Lean 4 proof is in the busy-beaver-explorer repository.

The machine builds a binary counter on its tape, like a car's odometer but in base 2. Between the counter's bits sit long stretches of tape, and each of these stretches works like a fuel tank: it slowly drains as the counter ticks, and the further left a tank is, the more slowly it drains. Most of the time the counter just counts. Now and then a tank runs dry, or every bit becomes 1 and the counter overflows, and the tape gets reorganised for a few steps before the counting resumes. At the far left end sits a small leftover word that every overflow nibbles away. When it is gone, the next overflow's carry has nowhere to go: it falls off the left end of the tape, and that is where the halting transition is.

Summary

Result Halts (proof submitted, under review)
bbchallenge ID 172044
Steps to halt ≈ 8.53 × 10131 (exact value below; computed, not part of the proof)
Visits to the right end about 9.6 × 1065
What it does A binary counter whose bits sit between slowly draining "fuel tanks"; the final carry falls off the left end of the tape
Proofs Rocq (busycoq #76, submitted); Lean 4 (busy-beaver-explorer)

Exact number of steps (132 digits; bbchallenge count, the halting transition included):

853177647932005270554892218084645935472995035642746848454477793277027802995098762076895667304703808111420498351739937140047615589683

Transition table

0 1
A 1RB 1RD
B 1RC 1RB
C 1LD 0RA
D 1RA 0LE
E 1LF 0LC
F --- 1LE

The machine halts when it is in state F and reads a 0. State F is only entered from state E reading a 0, which writes a 1 and moves left. So a halt needs two 0s side by side, and inside the written tape that never happens. It can only happen at the left edge, when the head steps off the written tape onto blank cells. So the question "does it halt?" is the same as "does the head ever run off the left end of the tape in state E?"

Behaviour

The tape each time the head reaches the right end, for the first 34,000 steps (one row per visit, time running downward). The tape grows steadily to the right. The fine striped texture is the word 011 repeated many times; the thin breaks in it are the bits of the counter.

The basic rhythm

The head shuttles back and forth. Each time it reaches the right end of the tape, it steps onto a fresh blank cell in state A and the tape grows. We call each such arrival a visit. There are about 9.6 × 1065 visits before the machine halts. Between visits, the head walks left into the tape, does some work, and walks back.

Reading the tape

Almost all of the tape is the three-cell word 011 repeated many times. Between these long repeated stretches there are short two-cell words. So the tape breaks into two kinds of pieces:

  • tanks: long runs of 011. The size of a tank is how many copies of 011 it has.
  • bits: the short words between tanks. Most of the time each one is either 11, read as 0, or 01, read as 1. Together they form a binary number, with the rightmost bit as the lowest.

For example, here is the tape at visit 59, written out piece by piece:

Piece tank bit tank bit tank bit tank end
On the tape 011 × 11 01 011 × 8 01 011 × 5 01 011 × 45 0, then the head
Value size 11 1 size 8 1 size 5 1 size 45

So at this moment the tanks have sizes 11, 8, 5 and 45 (left to right), and the three bits are 1 1 1.

A binary counter

Each visit adds 1 to that binary number, exactly as you would by hand:

  • starting from the right, every bit that is 1 turns into 0 (the carry);
  • the first bit that is 0 turns into 1, and the head turns back there.
Example: three bits, four visits in a row
Visit Bits (left to right) What the head does
1 0 0 0 → 0 0 1 Turns the lowest bit on; walks past one tank and back
2 0 0 1 → 0 1 0 Carries one place; walks past two tanks and back
3 0 1 0 → 0 1 1 Turns the lowest bit on again
4 0 1 1 → 1 0 0 Carries two places; walks past three tanks and back

The head only walks as far left as the carry goes. So most visits turn back after one or two tanks, and long walks become rarer the further left they go: reaching bit j happens only once every 2j visits.

Tanks that drain

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

The tanks change along with the bits. Every time a bit turns on, the tank just to its right loses one unit. (A unit is three cells, one copy of 011. This is after a small correction for the bits themselves: a unit also moves along with each bit that changes.) Meanwhile the rightmost tank gains 2 at every visit. The result:

  • The rightmost tank grows quickly.
  • Every other tank drains, and each tank drains half as fast as the one to its right, because the bit next to it turns on half as often.

So a long counter can run for an astronomically long time, roughly 2 to the power of its number of bits, before any tank gets low. The proof uses this to skip ahead: any number of ordinary visits can be done at once with a formula.

When things get irregular

Two things interrupt the clean counting:

  • A tank runs dry (it gets down to a few units).
  • The counter overflows: every bit is 1, so the carry runs all the way past the leftmost bit into whatever is at the left end of the tape.

During these events the short words between tanks briefly become other words (such as 11101 or 1101101101), and tanks merge or split. After a few visits the tape is a clean counter again, usually with different sizes. No formula is known for these events, so they are simply simulated step by step. There are 116,906 of them in the whole run, with ordinary counting in between.

How it ends

The leftmost tank drains slowest of all: it loses one unit only when the whole counter overflows. It ran dry four times, at roughly 105, 1014, 1039 and 1066 visits.

The first three times, the tape recovered: the next tank simply became the new leftmost one. The fourth time, a leftover word 11101101111101111 was stuck at the left end, and each overflow after that ate a piece of it:

11101101111101111 → 11101101111101 → 11101101101 → 1101101 → 11111101111 → 11111101 → 11101111 → 11101 → 1111 → 1

By then the counter had 214 bits (with 215 tanks), so each overflow took an enormous number of visits. Finally, at visit 9.6 × 1065, all 214 bits are 1 and only a single 1 is left at the left end. The next visit's carry runs through the whole counter, through that last 1, and onto blank tape. There state E reads a 0 and moves left, and state F reads another 0: the machine halts. This last walk across the tape alone takes about 2.9 × 1066 steps.

Where the huge number comes from

  • About 9.6 × 1065 visits happen before the end, because a counter with 214 bits takes about 2214 ≈ 3 × 1064 visits to overflow even once.
  • On every visit the head walks across the rightmost tank, and that tank grows by 2 at every visit. So the total number of steps grows roughly like the square of the number of visits: (9.6 × 1065)2 ≈ 9 × 10131, close to the exact 8.53 × 10131.
Words used on this page
Word Meaning
Visit The head stepping onto a fresh blank cell at the right end of the tape.
Tank A long stretch of the word 011 repeated; its size is the number of copies.
Bit The short word between two tanks: 11 = 0, 01 = 1.
Carry The run of 1 bits turning into 0 during a visit.
Overflow A visit where every bit was 1, so the carry runs past the leftmost bit.

Proof of halting

The proof follows the story above, with each part checked by a proof assistant.

  1. One visit. The counting rule (bits, carry, tanks) is proved for any number of bits, any tank sizes, and anything to the left.
  2. Many visits at once. A formula for any number of ordinary visits is proved, valid as long as the counter does not overflow and no tank gets too low.
  3. A fast simulator that stores the tape as runs of repeated words. Every move it makes is proved to match the machine. It uses the formula where it applies (checking the conditions each time) and plain simulation elsewhere.
  4. One run of this simulator from a blank tape reaches the halting transition, so the machine halts.

The simulator's own choices need no trust: whatever it does is covered by the proofs. The exact step count is not part of the proof; three separately written exact simulators give the same number.

Proof status

  • Rocq (Coq): submitted to busycoq as pull request #76 (November 2026). A port of the Lean proof with two extra block rules; the evaluation is vm_compute checked by Rocq's kernel in under 3 minutes, and it uses no axioms. Not yet reviewed or merged.
  • Lean 4: theorem halts in holdouts/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/lean/Halt.lean of busy-beaver-explorer. The rules and the simulator's soundness are checked by the kernel; the evaluation (about 6 minutes) 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