Busy Beaver Explorer / holdouts / 1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB / explained
A 6-state Busy Beaver machine · Status as of 16 November 2026.1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB
Decided: it haltsProved in this repository, checked by Lean and by Coq. The ledger below says what each part rests on.
It halts, after about 1.27·10758 steps. The machine keeps a ladder of counters at the right end of its tape. Each counter is invisible to everything left of it, so the far left of the tape runs the same program in extreme slow motion. There the ladder's tail eats the remains of an earlier ladder; when they are used up, the head steps off the left end of the tape and the machine stops.
halt : halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in holdouts/1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB/coq. Coq 8.18 compiles it and Print Assumptions reports no axioms; the build log is next to the files. It needs no direct run first: the verified accelerated run starts on the blank tape and takes about 30 seconds; the whole file compiles in about 2 minutes. The same files are on a branch of our fork of busycoq, ready to be proposed upstream: project-thread-3u4y3s.Each entry says what to write, which way to move and which state to enter. The machine starts in A on a blank tape (all 0s).
The machine stops when it is in C reading 0. C is entered only from B0 (writes 0, moves L): 0 B>0. So a halt is the moment this pattern appears, with the head on the cell after >.
| state | reads 0 | reads 1 |
|---|---|---|
| A | 1 R B | 1 L E |
| B | 0 L C | 1 R E |
| C | halt | 1 L D |
| D | 0 R D | 1 L A |
| E | 0 R F | 1 R F |
| F | 1 R A | 0 L B |
read:write move. Red marks a halting transition. Hover a state or a row to single out its arrows.This is the real machine, simulated in your browser. Step it, play it, or jump to a step count. Below the cells is the whole visited tape in the notation of the notes: 1^5 is five 1s, and C>0 is the head in state C on a 0.
(10)7 is the word 10 seven times in a row, and the orange tag is the head. The grouping is found afresh at every step by looking for the longest repeat of a word of up to 8 cells, so it shows the counts a machine keeps on its tape without anyone having to decode them first; it is a display, not a result.The diagram stacks the tape at many moments. Sampling at each new cell shows the shape of the run as the visited region grows; sampling evenly in time shows where the head spends its time. The records list every step at which the head reaches a cell no earlier step reached, with the side, the width so far and the whole tape: the first place to look for a repeating macro structure. Click a row of the diagram to send the simulator above to that step.
The question "does this machine halt, and when?" can be asked at four levels of description. Each level keeps less detail than the one above it and has a coarser unit of time, and each step down is a theorem saying that the lower level does exactly what the machine does. At the bottom, a function that keeps the ladder as numbers runs from the tape of visit 3,040 to the halting transition; that evaluation, with the theorems, is the proof (the bottom line).
4^n s and a tail. One unit is one hit (two visits); a level moves to the next of 16 positions, in 112n + c or 56n + c steps.hit0 … hit15
Level 3The ladder as an odometer
stack_run
Level 4The accelerated run
loop_sound
The two evaluations at the bottom, the plain run of the first 27,172,911 steps (fsteps0) and the
accelerated run (run0), are done by Lean's compiled code (native_decide); everything above
them is checked by the kernel. A Coq proof makes the same argument with its run checked by its kernel.
Pick a visit after the last reset. The browser runs the real machine from blank tape to that visit and reads its tape; separately it runs the accelerated model from visit 3,040, with every level kept as two numbers, to the same visit. The rows show the same instant at each level; the marks say whether the two computations agree.
Left of the start, the visited part of the tape stopped growing in the second half of the run (bounded so far, or growing so slowly that no record fell in the last half). Right of the start it grows like the square root of the step count, the signature of a head sweeping back and forth across the whole tape and adding a cell or a few at the end of each sweep (a bouncer-like shape) (fitted exponent 0.527).
After 109 steps the tape spans 41,692 cells (5 left of the start, 31,830 right), with a density of 1s of 0.725.
The tape (run-length coded, 1^5 is five 1s, C>0 the head in state C on a 0) at some of the last moments the head reached a new cell, cut to 400 characters:
| side | step | tape |
|---|---|---|
| right | 956,197,639 | 1^10 0 1 0 1^3 0 1 0 1^3 0 1 0 1^7 0 1 0 1^3 0 1 0 1^3 0 1 0 1^7 0 1 0 1^7 0 1^7 0 1 0 1^3 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^11 0 1 0 1^3 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^3 0 1 0 1^3 0 1 0 1^7 0 1 0 1 |
| right | 971,918,359 | 1^10 0 1 0 1^3 0 1 0 1^3 0 1 0 1^7 0 1 0 1^3 0 1 0 1^3 0 1 0 1^7 0 1 0 1^7 0 1^7 0 1 0 1^3 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^11 0 1 0 1^3 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^3 0 1 0 1^3 0 1 0 1^7 0 1 0 1 |
| right | 987,551,383 | 1^10 0 1 0 1^3 0 1 0 1^3 0 1 0 1^7 0 1 0 1^3 0 1 0 1^3 0 1 0 1^7 0 1 0 1^7 0 1^7 0 1 0 1^3 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^11 0 1 0 1^3 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^7 0 1 0 1^3 0 1 0 1^3 0 1 0 1^7 0 1 0 1 |
These are measurements of one bounded run, sorted by tools/py/bbtools/triage.py; the macro structure behind them is the next thing to find.
Stop the machine each time its head, in state A, stands on the blank cell right of everything it has written (a visit). Read the tape from the head leftwards two cells at a time: X is the pair 0 1, Y is 1 1; nothing else occurs. Write the lengths of the runs of Y between the X's as digits, so 2 1 4 4 is Y Y X Y X Y Y Y Y X Y Y Y Y. Each visit makes the word one pair longer.
At every second visit the word has the same build:
front 4^n1 s1 4^n2 s2 ... 4^nk sk tail
The front is 2 1 or 5, in turn. A level is a rung of n blocks 4 (on the tape: 0111111111) followed by a separator s, one of eight short words. The tail is what is left over, down to the blank left end. Going from the front 2 1 the head makes what we call an H-hit on the rest of the word, from 5 a V-hit; then a short visit of 8 steps turns the front into the other one.
The separator and the kind of the next hit give a level 16 possible positions. A hit always moves it to the next one:
| position | separator | hit | what the level does | rung |
|---|---|---|---|---|
| 0 | 0 1 0 1 | H | absorbs | |
| 1 | 0 3 1 | V | absorbs | |
| 2 | 7 1 | H | passes on an H-hit | |
| 3 | 5 3 | V | absorbs | +1 block |
| 4 | 0 6 | H | passes on a V-hit | |
| 5 | 0 1 0 1 | V | absorbs | |
| 6 | 5 0 1 | H | absorbs | |
| 7 | 7 1 | V | passes on an H-hit | +1 block |
| 8 | 0 1 3 | H | absorbs | |
| 9 | 0 6 | V | absorbs | |
| 10 | 10 | H | passes on a V-hit | |
| 11 | 5 0 1 | V | absorbs | +1 block |
| 12 | 0 3 1 | H | passes on an H-hit | |
| 13 | 0 1 3 | V | absorbs | |
| 14 | 5 3 | H | absorbs | |
| 15 | 10 | V | passes on a V-hit | +1 block |
So the ladder is an odometer: the first level turns with every hit of the front, the second with 6 of every 16 hits of the first, and so on. This table is proved in Lean for every rung length and every surrounding tape (lean/Levels.lean).
Kernel hit0 … hit15 in lean/Hits.lean: for
every block count n ≥ 1 and every tape to the left, a hit on a level at position p moves it to position p + 1,
adds the block at the four marked positions, and takes 112n + c (H-hit) or 56n + c (V-hit) steps inside the level; at
the six passing positions it makes exactly one hit of the stated kind on the rest. They are assembled from
lean/Levels.lean, one theorem for each stretch of the hit between two crossings of the level's borders.
The front itself is frontH and frontV: 107 and 83 steps per hit, the bounce visit included.
Choose a position and a block count; the browser writes the front, the level and a rest on a tape, runs the machine through the hit and the bounce, and compares what it finds with the table. The steps inside the level are counted by watching the head cross the level's two borders.
A hit on the part of the tape left of some border is always the same short list of calls: the head crosses the border in a certain state and later comes back in a certain state (for a V-hit: in C, back in E; for an H-hit five calls). A level looks at what is to its left only through these calls. And it passes on H-hits and V-hits in turn, exactly as the front does.
So the tape left of a level behaves exactly as if the front stood directly before it. It only gets its hits more rarely. That makes an exact shortcut possible: keep each level as two numbers (position and rung length), computed with exact integer arithmetic, and run the real machine, cell by cell, only on the front followed by the tail. Step counts stay exact too, because a hit costs 112 n + c or 56 n + c steps inside a level with n blocks. py/accel.py does this, and lean/Ladder.lean does it again as a function proved correct; up to step 1011 its visit numbers and step counts are those of the plain simulator.
Kernel In lean/Ladder.lean, level_run does y hits on one level
by induction on y, with closed forms for its position, block count, the hits it passes on and its steps
(advF, passF, costF; 16 hits are one turn: 4 blocks more, 6 hits passed on,
1344(j + 1) + d steps). stack_run, the transparency lemma, does y hits on a whole ladder by induction on
the list of levels: every level moves by its closed form, and the hits that come out at the bottom are a run of hits
on the tape below, exactly as if the front stood right before it.
The panel takes the tape of visit 6,000 (six levels and a tail) and makes y hits from the front. On the left of each row is what the closed forms say, level by level; then the browser checks it twice: by moving each level one hit at a time through the table, and by running the real machine for 2y visits. For the tail it runs the machine on the front and the tail alone, for as many hits as came out at the bottom, and compares.
A hit that reaches the blank left end of the tape comes back in an unusual state, and that flattens the ladder: one sweep turns every block 4 into 0 3. It happened at visits 3, 11 and 25 and, with a ladder of six levels, at visit 3,006 (step 27,167,343). After a reset a new ladder grows at the right end, and the flattened blocks are fuel for its tail. In a cycle of 12 hits,
7 3 3 > 5 4 0 4 > 4 0 7 0 4 > 4 0 1 0 1 0 3 4 > 4 4 0 1 3 0 1 4 7 > 5 4 7 > 11 7 > 4 0 1 0 1 0 10 > 4 5 3 0 1 0 1 0 1 0 3 3 > 5 0 1 0 1 0 3 3 > 7 1 0 1 0 3 3 > 4 0 1 3 0 3 3 3 > 7 3 3
the tail uses up two fuel blocks and leaves three new levels behind. But every new level makes the hits on the tail 8/3 times rarer. The fuel left by the reset of visit 3,006 is about 590 blocks, enough for 887 levels: the tail needs about (8/3)887 ≈ 10378 visits to eat its way to the left end, and a visit by then takes about 10379 steps.
Kernel The proof does not follow the tail by hand. loop in
lean/Ladder.lean is py/accel.py again, as a Lean function: it reads levels off the cells
behind the front and keeps them as numbers (opPeel), jumps to the next hit that reaches the cells
(opAdv; how far is computed by readyCount, which needs no proof because a wrong count makes
the step fail), makes that hit on the cells with a small simulator (tailHit), and when the calls do not
come back as a level expects it writes the deepest level out as cells again and retries (opUnpeel).
loop_sound: if loop returns N from a configuration of the run, the machine halts after
exactly N steps. A wrong choice can make loop fail; it cannot make it return a wrong number.
The stepper is the same algorithm in the browser. It starts from the tape of visit 3,040, reached by running the machine for 27,172,911 steps, and each click makes hits that reach the tail; everything above the tail is moved by the formulas. While the run is still short enough, each state is compared with the plain machine.
The machine can only halt in state C on a 0, and C is only entered when B reads a 0 and steps left. Inside the tape every 0 stands alone, so this needs B at the blank left end.
When the fuel is gone, the tail is 0 3 1 0 3 1 0 5 with blank tape behind it, and an H-hit is due. Its first three calls come back as usual. In the fourth the head runs through the tail in state C, turns the last pairs over, and B arrives on the blank cell left of the tape: one step left, C reads a 0, and the machine halts. The halting step is given in the bottom line.
The earlier arrivals at the left end (visits 3, 11, 25, 3,006) came in other states and only reset the ladder.
How many steps. The halting step is known exactly (see the bottom line): about 1.2736·10758, so between 10758 and 2·10758. The Lean proof states it (halt_step), and two independent programs give the same number. A rough estimate explains its size: the halt comes at visit 6.46·10378, which is about 9.3·(8/3)887 because each of the 887 levels gets 3/8 of the hits of the one above it. The tape grows by about two cells per visit, and each visit runs over the whole tape, so the step is about 3·(visits)2. The Coq proof shows that the machine halts but does not count steps.
Kernel last_visit_halts in lean/Levels.lean: the last visit on the
word without its 887 levels, 2 1 0 3 1 0 3 1 0 5 with blank tape to the left, reaches a halting
configuration after 278 steps. With the levels in between, the halt comes in the same call, later by the steps each
level makes before it (haltUp_sound, frontHalt_sound, and the constants of
level_halt). The picture is that visit, run in the browser: one row per step, time going down, the head
in orange.
The machine 1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB halts from a blank tape, at step
127357002621565065257620436683386936787539470067051886613218118511080673366941072419030003169655065867449076569424641011574489482373465883365675526698891984731533897533200967458271672457393649647114596314125471135660566111943361843730621394792642277333936847623104308961000089724168905591219305595735931713864752589517911334410100233581671754237003517860991278921217226890440796227582950616514639336930819296066429511864899248696946158576194825836402868940605014639617724789550009265777033152525606033456073540691727721901256364141236872161550422869463852043401520343212555953181130714885650835768030318277837531565019874900364467386746214009188503718874282272725926187590284697947001726343238522323981475257408390954658553165337971013334254732281910474403686
(bbchallenge count, the halting transition included; 759 digits, about 1.27·10758), in state C on a 0, two cells left of the leftmost 1, during the visit after visit number 6.457·10378, with 887 levels on the tape.
| statement | where | what it rests on |
|---|---|---|
halts : HaltsFromBlank, halts_in : ∃ c, steps haltN init = some c ∧ step c = none, halt_step : haltN + 1 = 1273570026…4403686 (Lean) | lean/Halt.lean | native_decide the kernel for the level rules, the ladder (stack_run) and the soundness of the run (loop_sound); Lean's three standard axioms; and two compiled evaluations: fsteps0 (the first 27,172,911 steps, to visit 3,040) and run0 : loop 100000 true s0 = some haltN |
halt : halts tm c0 (Coq, busycoq's definitions) | coq/M_1RB1LE_0LC1RE_HHH1LD_0RD1LA_0RF1RF_1RA0LB.v | Kernel no axioms (Print Assumptions halt: closed under the global context); the one long evaluation, loop 10000 true s0 = true, is checked by Coq's kernel. It proves that the machine halts, not when. |
So the exact step rests on the Lean theorem halt_step, with its two native_decide
evaluations; that the machine halts at all is also a Coq theorem checked by its kernel alone. Two separately written
programs (py/accel.py and verify/) give the same step.
The accelerated run of the proof, written again in JavaScript with exact big integers: first the plain machine
to visit 3,040, then hits on the tail with the levels as numbers, until a hit does not come back. It takes a few
seconds. At the end it checks the last visit: on eight small tapes that have the same 887 levels at their final
positions but only 1 to 9 blocks each, followed by the final tail, the plain machine must halt after exactly the
number of steps the formula gives (py/accel.py last).
The halt is a theorem checked by the proof assistant Lean (halts in lean/Halt.lean). It has three parts:
native_decide).A second proof, in Coq, without compiled evaluation. The same argument is also written in Coq on busycoq's own definitions (halt : halts tm c0 in coq/M_1RB1LE_0LC1RE_HHH1LD_0RD1LA_0RF1RF_1RA0LB.v). The hit on each level is proved by busycoq's symbolic execution for every rung length; the ladder lemma and a checked shortcut simulator are proved as in Lean, without step counts; and the one long evaluation is checked by Coq's kernel. Three changes make it fast: the shortcut run starts on the blank tape, so the 27-million-step plain run is not needed (the resets go through the same code); turns of 16 hits use bit shifts; and up to 64 hits that reach the tail are made in one pass over the 887 levels. The run then takes about 30 seconds, and the whole file compiles in about 2 minutes.
Before the theorem there was the same result from two independent programs (py/accel.py and the re-computation in verify/), compared with plain simulation at more than 12,000 checkpoints; they give the same step.
Status as of 16 November 2026. The same list as the proof-status page, built from the same file.
lean/Halt.lean, lean/Ladder.lean; python3 py/accel.py, halt.txtThe accelerated run from blank tape ends in the halting transition C0, two cells left of the leftmost 1, at step 127357002621565065257620436683386936787539470067051886613218118511080673366941072419030003169655065867449076569424641011574489482373465883365675526698891984731533897533200967458271672457393649647114596314125471135660566111943361843730621394792642277333936847623104308961000089724168905591219305595735931713864752589517911334410100233581671754237003517860991278921217226890440796227582950616514639336930819296066429511864899248696946158576194825836402868940605014639617724789550009265777033152525606033456073540691727721901256364141236872161550422869463852043401520343212555953181130714885650835768030318277837531565019874900364467386746214009188503718874282272725926187590284697947001726343238522323981475257408390954658553165337971013334254732281910474403686 (bbchallenge count). The last trip of the head to the left starts at right-end visit number 6457109013376761952964397678097307615669340968993585759245814706743742046125940261247241066403890938492170138345021775414788657246855473619762555399924006808185668177937261822888303321241424388506815212830693515134376015491900870498530843289643797903974663993452480048769041949957161985409468353341199468784692405027220745645833011312600661412072060494393516371733163287212276888; the tape then has 887 levels and is about 1.29·10379 cells long. In Lean: halts : HaltsFromBlank and halts_in : ∃ c, steps haltN init = some c ∧ step c = none, where haltN + 1 is the step above (the bbchallenge count includes the halting transition). The proof has three parts. (1) reach0: 27,172,911 steps from blank tape lead to the tape of visit 3,040, after the last reset (native_decide on the library's list simulator). (2) loop_sound (kernel): a function loop that keeps the levels as pairs of numbers and simulates only the cells left of them returns, from a configuration of the run, the number of steps to a halting configuration. (3) run0: loop returns haltN from that tape (native_decide; 3,539 simulated hits, 587 times the deepest level is written out as cells again, exact arithmetic on numbers of up to 759 digits). The axioms of halts are Lean's three standard ones and the two native_decide evaluations.
coq/M_1RB1LE_0LC1RE_HHH1LD_0RD1LA_0RF1RF_1RA0LB.v, coq/build.sh, coq/build.loghalt : halts tm c0, with busycoq's TM, halts and c0. The 16 level hits, the 9 halting hits and the two fronts are proved for every block count by busycoq's symbolic execution; stack_run (any number of hits on any ladder) and loop_ok (a shortcut run that keeps the levels as numbers and simulates only the tail cells, sound by construction) are ordinary proofs. The run from the blank tape, loop 10000 true s0 = true, is one evaluation checked by Coq's kernel (about 30 seconds; it makes no plain run of 27 million steps first and batches up to 64 tail hits per pass over the levels). Print Assumptions halt: closed under the global context. Coq 8.18.0, about 2 minutes for the file; too little fuel makes the check fail.
lean/Odo.lean, lean/Hits.lean (from py/hits_lean.py), lean/Ladder.leanA call on a tape T is a run that enters T in one state and leaves it in another, whatever lies to the right; a V-hit is one call, an H-hit five. hit0 … hit15 (from the stretch theorems): a hit on a level with j + 1 blocks at each of the 16 positions is such a hit, takes 112(j+1) + c or 56(j+1) + c steps inside the level, leaves the level at the next position, and at the six passing positions makes exactly one hit on the rest. level_run: y hits in a row on one level, with closed forms for position, block count, hits passed on and steps (16 hits are one turn: 4 blocks more, 6 hits passed on). stack_run: by induction on the list of levels, y hits on a whole ladder act level by level as the table says and pass the remaining hits to the tape below. front_run: the front and its two visits per hit. haltUp_sound, frontHalt_sound: a hit below the levels that halts (in its first call, or in the fourth call of an H-hit) is a halt of the machine, with the steps made in every level before it.
lean/Ladder.leancrun_sound, hrun_sound: a simulator for one call on a finite tape (blank beyond), correct for every tape to the right of the call. opAdv_sound (a jump of y hits of which none or one reaches the simulated cells), opPeel_sound, opUnpeel_sound (cells read as a level, and back), opFinal_sound (the hit that halts) and loop_sound: if the run is at the configuration of a state after its step count, and loop returns N from that state, then the machine reaches a halting configuration after exactly N steps from blank tape. Which levels to read and how far to jump is chosen by code that needs no proof: a wrong choice can only make loop fail.
verify/README.md (mymodel.py, myrun.py, final.py, sim2.c)A second implementation of the level odometer, written separately (its own cell simulator, its own measured step constants, the deepest level always simulated cell by cell), gives the same 887 levels, the same tail, the same last visit and the same 759-digit halting step. Direct simulation agrees with the accelerated run at 12,169 checkpoints in 440 windows spread over the whole run (visit number, step count and whole tape), and about 80 truncated endgames run directly to the halt stop at exactly the predicted step (the longest after 4,568,217,938,175 steps). Not observed directly: anything between step 1.2×1012 and the halt with more than about 14 levels on the tape; that part is covered by the Lean theorem above.
lean/Levels.lean (from py/levels_lean.py)A level 4n s is the cells s (0111111111)n. For each of its 16 positions and each stretch of a hit between two crossings of the level's borders, the machine's run is proved for every n ≥ 1 and every tape left and right of the level (63 theorems). A 64th and 65th theorem, last_visit_run and last_visit_halts, run the last visit on the word with all 887 levels removed (2 1 0 3 1 0 3 1 0 5, blank to the left): it halts after 278 steps. The generator checks that the stretches chain as the table says: the states in which the head leaves and comes back, that an absorbing level never touches the tape to its left, and the level after the hit.
python3 py/accel.py levelsFor 16 positions, 28 block counts (1..24, 40, 77, 200, 1000) and 13 different tapes to the left: the double visit of front + level + rest gives the level of the table and the rest that the front alone would have made of it, the head crosses the borders in the listed states, and the steps inside the level are 112 n + c (H-hit) or 56 n + c (V-hit). 5,656 cases.
python3 py/accel.py check, c/visits.cAt all 291 compared visits up to step 1.18·1011 the accelerated run has the visit number and the step count of a direct cell-by-cell run, in three variants (0, 1 or 2 levels kept in the simulated word; started at visit 3,040 or 600). The run started at visit 600 meets the reset of visit 3,006 at the right visit.
python3 py/accel.py --defer 1 (2, 3)Keeping the 1, 2 or 3 deepest levels in the simulated word (each level is then run cell by cell for its first hits, and no level ever has to be put back) gives the same 887 levels, the same tail, the same visit number and the same halting step.
python3 py/accel.py lastEight tapes with the 887 levels at their final positions, small block counts and the final tail 0 3 1 0 3 1 0 5: the direct run halts in C at the left edge after exactly the number of steps the formula for the last visit gives.
step_none_iff, lean/Blank.leanThe machine stops exactly when it reads the symbol of a halting transition (C0); the generated statement covers every configuration.
blank_runs_kernel, lean/Blank.leanThe list simulator of the shared library, proved to agree with the machine's semantics, runs 10,000 steps from blank tape without a halt, evaluated by Lean's kernel.
blank_runs_native, lean/Blank.leanThe same run, evaluated by compiled code.
python3 -m bbtools.ctl 1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB 8 # from tools/pyClosed tape languages from windows of 4, 6 and 8 cells cover the run; each allows the halting transition C0 only at the left end (blank to the left) with the right side starting 0001, 000110, 00011001 respectively. Two abstract configurations in all.
lean/Rules.lean (from py/rules.py)Reading pairs from the head leftwards (X = 0 1, Y = 1 1): V(X U) = Y Y U; V(Y3j+1 X U) = X X (Y X X)j Y U; V(Y3j+3 X U) = X X (Y X X)j Y3 U; V(Y3j+2 X X U) ends in X Y4 U. For every j and every tape to the left, 28j + const steps.
edge_halts, lean/Rules.leanOn the tape 0∞ 0 1 1 1 1 1 A> the visit runs into the blank left end and halts after 17 steps. Not a tape of the run from blank.
py/vmodel.pyV(X U) = Y Y U, V(Y X U) = X X Y U, V(Y Y X X U) = X Y4 U, V(Y Y Y S) = X X Y V(S), V(Y Y X Y Y S) = X Y4 V(S): equal to the machine on 19,312 random words and on the 724 visits they cover among the first 1,012 of the run. The words starting Y Y X Y X follow further rules not yet written down.
c/mrun.cA direct simulator on blocks of 16 cells (a full lookup table, 3·109 steps a second) runs 1012 steps without a halt; the head comes to the left end only at steps 1,779 and 27,158,883.
python3 holdouts/1RB0LB_1RC0LA_1LB0RD_1RE1RD_1RB1RF_1LA---/py/deep.py run 240, verify; holdouts/1RB0LB_1RC0LA_1LB0RD_1RE1RD_1RB1RF_1LA---/data/deep.jsonA macro simulator (blocks of 10 cells, long runs of equal blocks crossed in one go; exact: every macro step is a run of the machine, counted step for step) ran from blank tape to step 60,000,783,412,981,265,560 without a halt. At this block size it gives the same state, head position and tape as the direct simulator after 2,000,002,519 steps. This is a bounded run and says nothing about later steps.
. /etc/profile.d/lean.sh # after scripts/setup-lean.sh
holdouts/1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB/lean/check.sh # about 4 minutes; Halt.lean is the theorem
cd holdouts/1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB/py
python3 accel.py # the run to the halt (20 s); --defer 1, 2, 3: the same result
python3 accel.py levels # the level table and step constants against the machine
python3 accel.py last # the last visit on small tapes, direct run against formula
gcc -O2 -o /tmp/visits ../c/visits.c && /tmp/visits 1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB 1e10 A 2 100000000 2 > /tmp/v.txt
python3 accel.py check /tmp/v.txt # visit numbers and step counts against the direct run
python3 levels_lean.py > ../lean/Levels.lean ; python3 hits_lean.py > ../lean/Hits.lean ; python3 halt_lean.py > ../lean/Halt.lean ; python3 rules.py > ../lean/Rules.lean
python3 words.py ; python3 vmodel.py 3000000
sh holdouts/1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB/coq/build.sh /path/to/busycoq # Coq proof; a checkout of the BB6 branch of ccz181078/busycoq; about 2 minutes