1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB

From BusyBeaverWiki
Jump to navigation Jump to search

1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB (bbch) (bbchallenge ID 23376) is a six-state, two-symbol Turing machine from the list of BB(6) holdouts. Started on a blank tape, it halts after about 1.27 × 10758 steps (the exact count has 759 digits). A machine-checked proof was submitted to busycoq in November 2026 (pull request #75) and is awaiting review. A Lean 4 proof that also gives the exact step count is in the busy-beaver-explorer repository.

The machine builds a counter on its tape that works like a car's odometer, with one twist. In a car, a digit carries to the next digit once every 10 ticks. Here each "digit" carries to the next one only 6 times in every 16 ticks, so every digit runs 16/6 = 8/3 times slower than the one before it. Meanwhile, at the far left end of the tape, the machine slowly uses up a supply of leftover material from earlier in the run. Each time it uses up a piece, the counter gains new digits and gets slower still. After 887 digits the supply is gone, the head steps off the left end of the written tape onto blank cells, and that is exactly where the machine's halting transition is.

Summary

Result Halts (proof submitted, under review)
bbchallenge ID 23376
Steps to halt ≈ 1.2736 × 10758 (exact value below)
What it does Builds a slow "odometer" on the tape while eating a finite supply of leftover blocks; halts when the supply runs out
Tape at the halt about 1.29 × 10379 cells
Proofs Rocq (busycoq #75, submitted); Lean 4 with exact step count (busy-beaver-explorer)

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

127357002621565065257620436683386936787539470067051886613218118511080673366941072419030003169655065867449076569424641011574489482373465883365675526698891984731533897533200967458271672457393649647114596314125471135660566111943361843730621394792642277333936847623104308961000089724168905591219305595735931713864752589517911334410100233581671754237003517860991278921217226890440796227582950616514639336930819296066429511864899248696946158576194825836402868940605014639617724789550009265777033152525606033456073540691727721901256364141236872161550422869463852043401520343212555953181130714885650835768030318277837531565019874900364467386746214009188503718874282272725926187590284697947001726343238522323981475257408390954658553165337971013334254732281910474403686

Transition table

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

The machine halts when it is in state C and reads a 0. In practice that can only happen at the left edge of the written tape. Inside the tape the 0s are always isolated (never two in a row), and the step before the halt is state B reading a 0 that has another 0 to its left. So the question "does it halt?" is the same as "does the head ever wander off the left end of the tape in the wrong state?"

Behaviour

The tape each time the head reaches the right end, for the first 123,000 steps (one row per visit, time running downward). The tape grows steadily to the right. The dark vertical bands are long runs of a repeated 10-cell block; each band is one "digit" of the counter described below.
The first 600 steps from a blank tape (time runs downward, black = 1, coloured pixel = head).

The basic rhythm

The head shuttles back and forth. Every time it reaches the right end of the tape it writes two more cells there, so the tape grows by two cells per trip. We call each arrival at the right end a visit. Every other trip is just a short bounce near the right end. The other trips go into the tape: always through the first stretch of it, often deeper, and very rarely all the way to the left end.

Reading the tape as a counter

Read the tape from right to left in pairs of cells. Almost all of it consists of one 10-cell block, 0111111111, repeated many times, with a few short separator words in between. The tape breaks into three parts:

  • On the right, a short front that switches back and forth between two shapes.
  • In the middle, a sequence of levels. A level is a long run of the 10-cell block followed by a short separator word. These are the dark bands in the picture above.
  • On the left, a tail of other material, which reaches all the way to the left end of the written tape.

Each time the head leaves the front and travels into the levels, call it a hit. Hits come in two alternating kinds, called H and V, which differ in which states the head is in as it crosses. A hit acts on the first level. The first level may absorb it, or it may pass it on to the second level, and so on.

An odometer with slow digits

Each level behaves like one digit of an odometer. Its separator word (one of eight short words) and the kind of the next hit together give the level one of 16 positions, 0 to 15. Every hit moves the level to its next position, and after 15 it goes back to 0. At 10 of the 16 positions the hit stops there. At the other 6, the level passes a hit on to the next level.

One full turn of a level (16 hits)
Position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Separator word 0101 031 71 53 06 0101 501 71 013 06 10 501 031 013 53 10
Kind of hit H V H V H V H V H V H V H V H V
Passes a hit on? H V H V H V
Run gets longer? ✓ ✓ ✓ ✓

(The separator words are written in a compressed notation: each digit counts the 11 pairs between two 01 pairs. The exact words do not matter for following the story.)

Two things follow from the table.

  • Each level is slower than the one before it. Level 1 receives every hit. Level 2 receives 6 out of every 16, level 3 receives 6/16 of those, and so on. Level k receives (3/8)k−1 of all hits.
  • Levels get longer as they work. Every 16 hits a level's run grows by four blocks. Busier levels are therefore longer, and each level is about 8/3 times as long as the next one.

A key fact makes the whole analysis possible. How a level reacts to a hit does not depend on what lies behind it: the rest of the tape only sees the hits that are passed on. So the part of the tape behind any level behaves exactly as it would if that level were not there, only more slowly.

The fuel: why it takes so long

Early in the run the head reaches the left end of the tape a few times (at visits 3, 11, 25 and 3,006, the last one at step 27,167,343). Each time it comes back in an unusual state and wipes the counter out: every 10-cell block in every level is rewritten as a shorter word, and the levels are gone. These flattened blocks are the fuel. After visit 3,006 there are nearly 600 of them, and they lie at the left end of the tape.

A new counter then grows on the right, and the tail starts to eat the fuel. It does this in a cycle of 12 hits. Each cycle uses up two fuel blocks and adds three new levels to the counter. But the tail only gets the hits that make it all the way through every level, and every new level makes those hits 8/3 times rarer. So each bite of fuel takes far longer than the one before.

In the end the counter has 887 levels. Eating the last of the fuel needs about (8/3)887 ≈ 10378 visits.

How it halts

When the fuel is gone, the tail is the short word 0 3 1 0 3 1 0 5 with blank tape to its left, and an H-hit is on its way through the levels. This time the head runs through the tail and off its left end onto blank cells. There state B reads a 0, moves left, and state C reads another 0. That is the halting transition. The machine stops two cells to the left of the leftmost 1.

Where the huge number comes from

  • The halt comes after about 6.5 × 10378 visits, set by the 887 levels: (8/3)887 ≈ 10378.
  • Each visit adds two cells, so the tape is about 1.3 × 10379 cells long at the end.
  • Every hit crosses the first level, which is the longest and grows in step with the number of visits. So the total number of steps grows like the square of the number of visits: about 3 × (6.5 × 10378)2 ≈ 1.27 × 10758.
Words used on this page
Word Meaning
Visit The head arriving at the right end of the tape; the tape gains two cells.
Front The short piece at the right end, which switches back and forth between two shapes.
Hit One trip of the head from the front into the levels; two kinds, H and V, alternate.
Level One digit of the counter: a long run of the block 0111111111 plus a short separator word.
Position Which of 16 states a level is in; every hit advances it by one.
Fuel Leftover short words at the left end, from the last time the counter was wiped out.
Tail The part between the last level and the left end, which eats the fuel.

Proof of halting

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

  1. The levels. The table of 16 positions is proved for every run length and for whatever lies on either side of the level.
  2. The odometer. By induction on the number of levels: any number of hits moves every level as the table says, and the tape behind the levels sees exactly the hits that are passed on.
  3. A fast simulation. A program stores the levels only as a list of (position, length) and simulates cell by cell only the front and the tail. It is proved that if this program reports a halt after N steps, the machine really halts after N steps. Started from the tape at visit 3,040, the program reaches the halt.

The Lean proof also gives the exact step count; the Rocq proof shows that the machine halts but does not count steps. Re-derivations with separately written code give the same 887 levels and the same 759-digit step count. About 80 shortened versions of the ending, run step by step without any shortcuts, stop exactly where the formula predicts.

Proof status

  • Rocq (Coq): submitted to busycoq as pull request #75 (November 2026). One file, no axioms, about 2 minutes to check. Not yet reviewed or merged.
  • Lean 4: theorems halts and halt_step in holdouts/1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB/lean/Halt.lean of busy-beaver-explorer. Lean's kernel checks everything about how the machine behaves for all sizes. The two long computations (the first 27 million steps, and the fast simulation) use 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