Busy Beaver Explorer / the holdout
What is proved about the holdout, and what is open
1RB0RE_1LC0RA_1LA1LD_1LA---_0RF0LB_0LD1RE
This six-state Turing machine is one of the BB(6) holdouts: nobody knows whether it halts when started on a blank tape. This page says where the formal proof stands, what is left, and how to check every part of it yourself.
Status as of 28 October 2026. The work is moving; this page is updated as results are merged into the repository.
In short
The question is not settled. What is proved, in Lean 4, is that if the machine ever halts from blank tape, its run must first reach an open clean tape: a clean tape of width at least 2⁴¹ whose width falls, at every depth, in a residue class that the clean-tape tree leaves open. At 36 binary digits these are 1,660,024 classes of W/2, together a fraction 2.4 × 10⁻⁵ of the widths. From that clean tape, one of two things must happen before the halt:
- a finer tree, which also stops at loop entries that can neither close nor end at a right end below 769 and whose chain keeps the middle wall far from the end, leaves it open too (1,255,963 of the classes, 1.83 × 10⁻⁵), and the run reaches two marks touching; or
- the run enters the machine's main loop and reaches a pass start (a round start with just three walls on the tape, the last one at distance R from the right end) with R ≥ 769 and its middle wall at least 15/64 of the width from the end, that the pass-start tree leaves open at every depth, and halts from there (only possible from the other 404,061 classes, 5.9 × 10⁻⁶). Pass starts that meet every one of these conditions, a width above 2⁴¹ included, and halt are proved too (
lane769_far_wide), so the conditions alone do not rule out a halt: what is open is whether the run reaches such a pass start. Taking the exhaustive C search below as given, the pass start is wider than 2⁶⁶, and there untrusted checks rule out every halting route found so far, whether it would end in a close or at any other right end below 178. But several of those routes' lanes belong to a family of lanes that goes on without end, and on its later lanes the same checks leave the paths followed there open at ever larger widths, so no floor closes it. On three of those lanes, pass starts wider than 2⁶⁶ that meet every one of these conditions and halt are proved too (loop3_far_66and two more). Keeping the family off needs an argument over a loop the run makes on four walls, together with where the run's own loop entries lead.
This is the theorem blank_halt_open_big, which sharpens blank_halt_open_small with the shape and the size of the pass start; blank_halt_open_far_kernel proves it with R ≥ 178 in place of R ≥ 769, from width 2²⁰ (2³⁷ for the pass start), using Lean's kernel alone, with no compiled code in the trusted base. Read backwards, as never_halts_of_big: if the machine halts from none of the configurations in 1 and 2, it never halts from blank tape. Separately, an exhaustive C computation shows that no clean tape narrower than 2⁶⁶ leads to a halt.
The run from blank tape, stage by stage
The machine's tape can be read as stripes 1010… with a few marks on them (gaps, markers, walls and blocks). Its run from blank tape passes through clean tapes (one marker at the end), sometimes enters an eight-round loop, and can only halt at a close at the right end or where two marks touch. The loop runs from pass start to pass start: round starts with just three walls, at a, b and W − R − 1 on a tape of width W, so that R is the distance from the last wall to the right end. Each full pass divides R by 16 and adds 24 to the width. The pass starts the loop lands on, one after another, form the loop's chain. Inside the loop the run can close only at a pass start whose R has come down to one of nine small values, from 2 to 176, with a matching residue, so a chain that ends at R ≥ 178 has left the loop without closing. The proof follows a halting run through every stage. Each stage below is labelled by what its proof trusts.
1. The mark rules and the round theorem
21 rules say how the machine moves the marks, for every stripe length and any surrounding tape, and one round of the machine is exactly one round of the mark model, or a halt exactly where the model says.
2. From blank tape to the first wide clean tape
The model is run from blank tape to the clean tape of width 2²⁰ (294,033 rounds), checked by the kernel; or to width 2³² (1.2 × 10⁹ rounds), after which every clean tape of width between 2³² and 2⁴¹ in an open class (26,508,327 of them) is run directly to a wider one.
3. From clean tape to clean tape: the clean-tape tree
Split by residue classes of W/2, at every depth: from a clean tape outside the cut classes the machine reaches a wider clean tape without halting. The plain tree follows the run through the loop round by round; a finer tree also stops at loop entries from which no member of the class can close or end at a right end below 769 (178 in the kernel-only version), and whose chain keeps the middle wall far from the end. Both are built by an explorer proved to build only valid trees, so nothing is evaluated.
4. Through the loop: exit, endgame, chain and σ bound
Every loop state runs without halting to a clean tape, a break of the end-meeting chain, or another pass (358 classes). Every pass start either has its right-end distance R in the closing set {2, 4, 8, 16, 24, 32, 48, 64, 176} with its left countdown L₁ in R's class, or runs on without closing until it leaves the loop or lands on the next pass start by one of three exact maps. By induction along this chain, a run closes through the loop only from such a pass start, and that gives the σ bound log₂W ≤ σ + 6.38.
5. Past the loop's end: pass-start trees
From a pass start where the chain ends, the run is followed on, outside the trees' cut classes, to the next landing of the chain or to a wider one-marker clean tape, at every depth, and there the clean-tape tree takes over again.
What remains: open clean tapes, then open pass starts
Configurations that a tree cuts at every depth are not followed further. A halt from blank tape must first reach a clean tape that the plain tree of step 3 cuts at every depth, and then either stay in the finer tree's cut classes or reach a pass start that the tree of step 5 cuts at every depth. From a checked loop entry the loop's chain ends at R ≥ 769, and every step keeps the middle wall far from the end, so that pass start has R ≥ 769 and 15W ≤ 64(W − b).
What is proved
blank_halt_open_big
A halt from blank tape needs a clean tape of width ≥ 2⁴¹ that the plain clean-tape tree cuts at every depth, from which the machine halts. Then either the finer tree (loop entries with the end and shape checks) cuts it at every depth too, and the mark model reaches a contact from it, or the run from it reaches a pass start with R ≥ 769 and 15W ≤ 64(W − b) that the tree for R ≥ 178 cuts at every depth, halts from there, and the model reaches a contact. It sharpens blank_halt_open_far (the same with R ≥ 178) and blank_halt_open_small (without the shape), which joins blank_halt_open (the open clean tapes come first) and blank_halt_small (no small right end). With the narrower closing classes below, at the clean tapes' loop entries and at the pass-start trees' close leaves, it holds as well, with the same pass starts left to rule out and clean tapes among those it leaves (blank_halt_open_big_close, and so for the two it sharpens).
lean/thm/BigEndHalt.lean, FarHalt.lean, OpenSmallHalt.lean, OpenHaltClose.lean · native_decide for the prefix and direct runs
blank_halt_open_far_kernel
The same with R ≥ 178, from width 2²⁰: the open clean tape is at least 2²⁰ wide; in the first case it is also cut by the finer tree when it is at least 2³⁷ wide, and the open pass start is at least 2³⁷ wide, with R ≥ 178 and 15W ≤ 64(W − b). Nothing is evaluated by compiled code; #print axioms lists only propext, Classical.choice and Quot.sound. There is no kernel-only version with R ≥ 769: from 2³⁷, where this tree starts, the bound on a round-7 break gives only 383.
lean/thm/FarHalt.lean · kernel
never_halts_of_big
The open question as two hypotheses. If the machine halts from no clean tape of width ≥ 2⁴¹ that both clean-tape trees leave open at every depth, and from no pass start with R ≥ 769 and 15W ≤ 64(W − b), left open at every depth, that the run reaches from a clean tape the plain tree leaves open, then it never halts from blank tape.
lean/thm/BigEndHalt.lean · native_decide, through blank_halt_open_big
No small right end past the loop
Full passes keep R³/L₁², and a round-7 break from width ≥ 2³⁷ lands with R³/L₁² > 177³/9, so past every loop entry that passes a small-end check (all 28,660 at 36 digits do) the loop's chain ends at R ≥ 178, never in the trees for R < 178. This places the open pass start, not the halt: past it the run could still enter the loop again and reach a halting class.
LoopChain.small_end, blank_halt_small in lean/thm/SmallEndHalt.lean · kernel
No right end below 769
From width 2⁴¹ a round-7 break lands higher, with 32R′ > 3 · 2⁴¹ and 96L₁′ < 12,320R′. A run of p full passes from there ends at a right end r only if R′ = 16pr and L₁′ = 64pℓ with ℓ ≥ 3, so for r up to 768, seven passes or fewer leave R′ too small and eight or more leave L₁′ too large beside it (break7_noEnd769). With the entry check raised to 769 (all 28,660 entries at 36 digits pass, and an untrusted run finds no end from 178 to 5,000), the chain's last pass start has R ≥ 769 (LoopChain.big_end, blank_halt_open_big). So every halting class with R below 769 is out of that pass start's reach, whatever the class's route.
lean/BB6/BigEnd.lean, lean/thm/BigEndHalt.lean · kernel for the chain and the entries, native_decide for the prefix and direct runs
Halting pass starts past 769
The bound on R does not exclude halts by itself. A census at every even R from 770 to 1,004 (untrusted) finds halting classes on the lanes of the smaller R and on three more, and on each lane a family with R ≥ 769 is proved to halt and to be left open at every depth, as is δ at R = 998 at each scale W − b = 2j − 2,654 from j = 13 to 30 (lane769_open_halt). So are 26 families on routes that census misses: ζ, a second route on δ's lane that first closes above the census's W − b ≤ 4,096, at R = 998 at eleven scales from W − b = 2¹⁴ − 2,654 to 2²² − 2,654, ε, ε′ and four more routes that a census at R = 5,002 to 5,862 finds, and a route at R ≡ 1,702 (mod 2,048) that a census at every R of a class finds (route769_open_halt), and 26 on one more lane that census finds (gamma769_open_halt). One member, with walls 449, 2,462 and 15,193 and width 16,192, also has 15W ≤ 64(W − b) (lane769_far). Each family fixes W − b, so its members have that shape only up to width 64(W − b)/15, which is below 2⁴¹ for all but two families, on the new lane at its scale 3 · 2³⁹. A member of one of these, with walls 449, 3,564,686,921,054 and 5,213,786,600,921, width 5,213,842,519,808 (about 242.2) and R = 55,918,886, meets every condition that blank_halt_open_big puts on the pass start, its width included, and halts (lane769_far_wide).
lean/thm/LaneHalt.lean · kernel
Halting pass starts above 2⁶⁶
On the lanes where the run makes two to five passes of a loop on four walls before it re-enters (below), six families of pass starts with R ≥ 769, each with its first wall free, are proved to halt and to be left open at every depth by the pass-start tree (loopFar_open_halt). On each lane and scale a member meets every condition that blank_halt_open_big puts on the pass start, the far shape and a width above 2⁴¹ included: at about 242.2 with two passes and 242.3 with three (loop2_far_wide, loop3_far_wide), and wider than 2⁶⁶, past the exhaustive search's floor, at about 267.4, 267.0 and 266.7 with three, four and five passes (loop3_far_66, loop4_far_66, loop5_far_66). An untrusted far-shape search found them; that they make exactly those numbers of passes is checked so far only on a branch not yet merged.
lean/thm/LoopFarHalt.lean · kernel
Every close at the right end is a halt
A close with the end marker at distance 0 that the mark model reaches is a halt of the machine 54 steps later (reach_close_halt). The pass-start trees' halting leaves form eight classes by residues of b and W: all of R = 2, 3/8 of R = 4, 1/8 of R = 6, and 1/32, 1/64, 1/128 and 1/256 of R = 8, 16, 32 and 48. Every pass start in one halts (pass_class_halt), and so does every pass start whose loop chain reaches one (chain_class_halt), such as one with R = 256 that lands at R = 32 and then in the R = 16 class (pass_halt_example_r256).
lean/BB6/CloseHalt.lean, lean/thm/PassHaltClasses.lean · kernel
Pass starts that reach a clean tape at once
Every pass start with gaps of at least 448, W ≡ 0 (mod 4), R a multiple of 4 from 8 up and b ≡ 2 (mod 8), so L₁ ≡ 4 (mod 8), reaches a one-marker clean tape wider than the start after five rounds, without halting, whatever its other walls and its width (pass_clean_l4). With R a multiple of 8 from 16 up and b ≡ 14 (mod 32), so L₁ ≡ 16 (mod 32), it does after seven (pass_clean_l16); the cases first proved, pass_clean8, pass_clean16 and pass_clean24, follow. At a pass start L₁ ≡ 10 (mod 14), so the only value with |L₁| < 10 is −4, and the last pass start before a halt at a right end r that is a multiple of 4 from 8 up has |L₁| ≥ 10, so R³/L₁² ≤ r³/100 there (pass_clean_small4).
lean/thm/PassClean.lean · kernel
Open pass starts that halt
Every pass start with walls at a, b and b + 467 and width b + 646 (so R = 178), with a odd, a ≥ 448, b − a ≥ 448 and b ≡ 2,010 (mod 2¹⁴), is left open by the tree for R ≥ 178 at every depth, and halts. Past its chain's end the run meets the end at 254, off the old chain, and that meeting halves 254, 126, …, 2, 0 to a close, through a pass start in the R = 16 class (family_open_halt). So there are such pass starts wider than any given width, above 2⁴¹ too (sym_open_halt, sym_open_halt_wide). Seven more families are proved the same way (open_halt_families), and the loop's chain can land on one after a full pass: from walls 449, 1,182 and 10,399 at width 13,376 (R = 2,976) to walls 3,187, 9,698 and 13,213 at width 13,400 (R = 186), a member of the eighth family (full_pass_open_halt). The eighth family's route works at every scale tried: for each j from 10 to 30, a family with R = 178 and W − b = 2j+2 − 378 meets the end off the chain at 2j − 2, halves to 0 and closes (reentry_open_halt). With R = 182 the same route works at these scales too (reentry6_open_halt), and a full pass lands on a halting pass start with R = 222 (full_pass_open_halt6). At R = 486 two lanes halt at each scale W − b = 212+s − 1,630 for s from 0 to 18 (lane486_open_halt), and four families with R = 230 halt with no other pass start on the way (no_pass_open_halt).
lean/thm/PassOpenHalt.lean · kernel
The pass start a halt needs is wide
Every step of the loop's chain keeps the middle wall far from the end: a full pass and a round-7 break land with 15W′ ≤ 64(W′ − b′), so the middle wall is at least 15/64 of the width from the end, and a half pass, only ever the first step, lands so too when the loop entry passes a second check. With both checked at the loop entries (all 28,660 at 36 digits pass), every pass start of the chain, the last one too, has 15W ≤ 64(W − b) (LoopChain.far_end, blank_halt_open_far). The 29 families of open_halt_families and reentry_open_halt keep R and W − b fixed, so they have even the weaker shape W ≤ 64R + 6 or 15W ≤ 64(W − b) only below width 2³⁵, and the run from blank tape halts through none of them (blank_halt_not_family).
lean/thm/WideHalt.lean, FarHalt.lean · kernel for the chain and the families, native_decide for the prefix and direct runs
The σ bound
A pass divides R³ and L₁² by the same factor, and every closing class has R³/L₁² ≤ 176³/256². So a close through the loop needs log₂W ≤ σ + 6.38, where σ = 3 log₂(W/R) + 2 log₂(|L₁|/W) at the start of the last run of full passes. From width ≥ 2²⁴ a close is p full passes after at most one half pass. The bound is attained (R = 2,816, L₁ = −16,384).
LoopChain.sigma, loop_halt_sigma, blank_halt_sigma, LoopChain.close_wide · kernel
An end meeting at distance 2 is not a close
The endgame trees stop at every end meeting at distance 2 or less, so the closing classes count meetings at distance 2 as closes. But after a meeting at distance 2 the halving chain puts the next one at distance 0, and when it is anywhere else the run has left the chain. Trees that run on past such meetings, for R = 8, 16, 24, 32, 64 and 176, show that a close from a pass start needs R in {2, 4, 8, 16, 32, 48} and L₁ in R's class: even for R = 2 and 4, a multiple of 32 for R = 8, of 64 for R = 16, and of 128 for R = 32 and 48 (endgame_stretch_close). There R³/L₁² ≤ 4, so a close through the loop needs log₂W ≤ σ + 2, and from width ≥ 2²⁰ it is p full passes after at most one half pass (loop_halt_sigma_close, loop_halt_wide_close). The end-to-end theorems are restated with these classes: at a loop entry the condition EntryNoCloseC excludes only them, and the pass-start trees for R below 178 take them at their close leaves, with the same cuts outside R = 8, 16, 24, 32, 64 and 176 (pass_halt_chain_close, blank_halt_open_big_close, above).
lean/BB6/EndgameClose.lean, lean/thm/EndgameCloseTheorem.lean, lean/thm/LoopClose.lean, lean/thm/PassHaltClose.lean, lean/thm/RouteEntryHaltC.lean · kernel
The loop chain
If the machine halts from a pass start with gaps ≥ 448, its run follows full passes (R → R/16), a half pass (only as the first step) and round-7 breaks through every landing whose gaps stay ≥ 448, at any width. Within the loop it closes only from a pass start in a closing class.
LoopChain, loop_chain_halt in lean/thm/LoopHalt.lean · kernel
The exit and the endgame
exit_stretch: every loop state with gaps ≥ 390 ends in one of 358 classes (298 breaks, 58 clean tapes, 2 passes). endgame_stretch: for every even R, the exact closing table. Both trees are checked by the kernel subtree by subtree, and each leaf ends at a stated event.
lean/thm/ExitTheorem.lean, EndgameTheorem.lean · kernel
The 64-digit exhaustive search
Every clean tape narrower than 2⁶⁶ reaches the next clean tape without halting: 205 billion settled classes and 662 billion direct runs, about 6.7 × 10⁵⁵ machine steps. Rerun to 60 digits with the corrected simulator (the "trailing wall" fix found by the formalization), it reproduces the original result line for line, the corrected case never occurring; a 128-bit copy of the fixed program then took it to 64 digits, matching the 60-digit run at every shared level.
csearch/nrefdfs2.c, csearch/nrefdfs2w.c, dfs/merged64.txt · C search
Also proved, and used along the way: the route tree for two-marker states (route_tree_clean, at every depth), and certificates with independent Python checkers for the exit (358 classes), the endgame (40,991 classes; 83,699 in either phase) and the route tree to 36 and 40 digits. Some of the open pass starts really do halt: every pass start with R = 6, b ≡ 2 (mod 8), W ≡ 2 (mod 4) and gaps ≥ 448 halts (pass_r6_halt, thm/PassHaltR6.lean). A differential test (simtest/) runs every simulator against the proved model.
What each result trusts
| Result | Open clean tapes start at | Trusted base |
|---|---|---|
blank_halt_open_far_kernel, blank_halt_open_far_kernel_close | 2²⁰ | Lean's kernel and the three standard axioms |
blank_halt_open_big, never_halts_of_big, blank_halt_open_far, blank_halt_not_family, and their versions with the narrower closing classes (blank_halt_open_big_close and so on) | 2⁴¹ | the above, plus Lean's compiler (and a C compiler) for native_decide on the prefix to 2³² and the 26.5 million direct runs |
| with the exhaustive search | 2⁶⁶ | the above, plus the C program nrefdfs2w; this combination is not a Lean theorem |
What is open
Exactly the two hypotheses of never_halts_of_big. Proving both would show that the machine never halts.
The open clean tapes
Every halting run passes one, so this is the main open case. At 36 digits the plain tree leaves 1,660,024 classes open over the widths ≥ 2⁴¹ (exactly the open classes of the exhaustive search), and their measure shrinks about 0.76-fold per digit. That it shrinks to zero is a measurement, not a theorem. In the surveys, what keeps a class open is a long run of rounds with only two or three marks, about one binary digit per round, which is the growth of the class tree itself. Taken apart, such a run is a word in about 14,000 exact return pieces from one two-marker state to the next. Each piece repeated is bounded, a reset by a never-zero countdown of its own and a pure halving by the marker's position (the eight largest pieces and their countdowns are Lean theorems), but the countdowns differ from piece to piece and chains of returns multiply about 1.66-fold per digit, so no single lock or integrality argument settles a class.
Deeper trees shrink the open part but do not close these classes. The tree with loop entries (cleanTreeGE, which at 36 digits leaves open the same 1,255,963 classes as the finer tree) leaves 6,582,732 classes open at 40 digits (measure 5.99 × 10⁻⁶) and 33,928,389 at 44 (1.93 × 10⁻⁶; native_decide, used by no theorem about the machine). Yet nearly every class open at a given number of digits still has a part open deeper down: 1,255,820 of the 1,255,963 at 36 digits do at 40 (untrusted). A class that keeps an open part at every depth holds 2-adic values of W/2 that no depth settles, and the tree tells an integer from the other 2-adic values only at the edge of its cone. So, as measured, no depth of the tree closes these classes.
Nor can a lock of the loop's kind, which uses that W is an integer (integ/INTEGRALITY.md). An open class holds not one such value, as the loop holds its fixed point, but a Cantor set of them: below every class open at 24 digits but 2, the tree of depth 36 still leaves 42 to 304 classes open (native_decide). A countdown like the loop's (L₁ is divided by 64 on each pass, and L₁ ≡ 3 (mod 7) is never 0) would have to vanish at all of these infinitely many points, so it would be zero, and the only invariant modulo an odd number is the count of 1s mod 3. What is left is to follow each width past the digits it has, and whether every width then settles is a question of the Collatz kind.
Do the open pass starts get reached?
Some pass starts that the pass-start trees leave open really do halt: one in eight of those with R = 6 leaves the loop at round 2 and closes in round 7 (for example walls 743, 1,802 and 3,319, width 3,326, halting after 11,362,209 steps); in Lean the whole class halts (pass_r6_halt). So no depth of these trees can close the case on its own. Every known halt from a pass start closes through one of the eight halting classes, all with R ≤ 48, and the loop's chain from a checked loop entry never ends in one: it ends at R ≥ 769 (blank_halt_small, blank_halt_open_big). So what remains are the pass starts with R ≥ 769 that their tree leaves open at every depth, from which the run could still reach a class by entering the loop again: an end meeting off the old chain starts a new halving chain. That does happen, from a pass start with R = 130 (pass_halt_example_reentry), and also with R ≥ 178: eight families halt this way, each with members wider than any given width, two more at each scale of the third gap from 2¹² to 2³² (R = 178 and 182), two with R = 486 at each scale from 2¹² to 2³⁰, four with R = 230 that halt with no other pass start on the way, and with R ≥ 769 a family on each lane a census finds there, δ at R = 998 at each scale from 2¹³ to 2³⁰, ζ at eleven scales from 2¹⁴ to 2²², one or two on each other route a census near R = 5,000 adds, five on one at R ≡ 1,702 (mod 2,048) and 26 on one more lane, and the tree leaves all of them open at every depth (sym_open_halt, open_halt_families, reentry_open_halt, reentry6_open_halt, lane486_open_halt, no_pass_open_halt, lane769_open_halt, route769_open_halt, gamma769_open_halt). An exhaustive scan of the widths 2,048 to 3,072 finds eleven placements of the walls that close, seven of which repeat at larger widths, with a period of 2¹³ to 2¹⁵ (untrusted).
So this question is whether the run from blank tape reaches such a pass start, not whether one halts. The pass start that blank_halt_open_big names is the last of a chain from a checked loop entry, so it has R ≥ 769, its middle wall is at least 15/64 of the width from the end, as at every pass start of such a chain, and it is wider than 2⁴¹. The bound on R puts every halting class with R below 769 out of its reach, whatever the class's route. Most families with R ≥ 769 are out of reach by the shape and the width: each fixes W − b, so its members have the shape only at widths up to 64(W − b)/15, below 2⁴¹ (for the one with R = 914, only below 58,502, blank_halt_not_family; the member of δ that lane769_far names has it at width 16,192). Two are not: on one lane at the scale 3 · 2³⁹, members with the shape at widths of about 242.2 and 242.7 halt (lane769_far_wide), so what is proved about the pass start does not exclude them, and the same holds for members on four lanes further out (loop2_far_wide and the others, above). With the exhaustive search in place of the Lean check of the clean tapes below 2⁴¹, the pass start would be wider than 2⁶⁶, past those near 2⁴² (below), but not past the three wider than 2⁶⁶ (loop3_far_66, loop4_far_66, loop5_far_66). A full pass can land on a family member at small widths (full_pass_open_halt, full_pass_open_halt6), but not where the chain from a checked loop entry ends. The run reaches such a pass start only after an open clean tape that meets a loop entry.
An untrusted census of halting classes, at many R from 178 to 1,004 and at eight R near 5,000, finds them closing by many routes, some with no pass start after the first. Two routes, δ and ε, recur at every R ≡ 486 (mod 512, or mod 1,024 for ε) tried and at every scale up to 2³⁰, so no bound on R reaches them. On each route the run comes to a last pass start whose R′ the lane fixes and whose L₁′ is affine in the start, so R′³/L₁′² there can be bounded over every pass start that blank_halt_open_big allows. Full passes keep R′³/L₁′², so it has to fit where the route ends. From a width of 2²⁴ a close at the chain's end is a run of full passes (LoopChain.close_wide), so its right end r is R′ divided by a power of 16 and its L₁ is L₁′ divided by the same power of 64, with r in the closing set and L₁ in r's closing class (closeClasses). On a lane R′ is 2i or 3 · 2i, and so is r, so a close allows R′³/L₁′² at most 4, or 13.5 at r = 24. The known halting classes lie among these closes, but for R = 6's, which needs W ≡ 2 (mod 4), and no pass lands with that. At any other right end r below 178 it is at most r³/16, as L₁ is even at a pass start, or r³/100 where r is a multiple of 4 from 8 up (pass_clean_small4, above). That rules out against a close, from any loop entry, 12 of the first 18 routes past 769 that the censuses found, and the other six, on two lanes, above width 243.7, or 254.1 against any end below 178 (untrusted, runs/lane_sigma.py; the routes' forms are observed on the model, not proved); with the close's own L₁ in place of the least its class allows, only two of the six, ε and ε′, are left (untrusted, runs/close_l1.py). With the narrower closing classes above, which blank_halt_open_big_close takes, a close allows at most 4, or 1.69 at r = 48, and leaves only ε and ε′, below width 241.1, and with the close's own L₁ none (untrusted, both scripts with --closeC). Below 243.7, a search of the six (run when a looser bound at the ends left them up to 252.7) finds no pass start with R ≥ 769, the far shape and width above 2⁴¹ (untrusted: on each route the census finds one closing class of b at each R, whose step in R is taken from three R and checked at three far R, up to R ≈ 1.1 × 10¹²). So if each step holds at every R of its class and the censuses see every class, none of these 18 routes takes the run to a halt from the pass start that blank_halt_open_big names, from any loop entry. The censuses had missed two of them, ζ and one at R ≡ 1,702 (mod 2,048), until run at every R of a class, and that run has since found paths on two more lanes: 21 on one, which R′³/L₁′² leaves up to width 253.7 against a close, or 251.1 with the narrower classes (264.1 against any end below 178), and 20 on another, up to 255.7, or 253.1 (266.1). On two of the first lane's paths the far shape occurs above 2⁴¹, at pass starts that halt (lane769_far_wide).
With the exhaustive search, the pass start is wider than 2⁶⁶ (untrusted): every clean tape narrower than 2⁶⁶ reaches the next one without halting, and with that in place of the Lean check of the clean tapes from 2³² to 2⁴¹, the same proof puts the open clean tape, and so the pass start, above 2⁶⁶. This does not follow from blank_halt_open_big as stated. Above that floor R′³/L₁′² rules out every route and path found so far against a close, and the first 18 routes against any end below 178 as well. Against such an end eight paths are left, all on the second new lane, at widths up to 266.1, with r³/100 at the ends that are multiples of 4 from 8 up, which is a theorem (pass_clean_small4); their ends would have to lie on one of three lines of pass starts, each with a fixed R and L₁, on which a census on the halting side finds only clean tapes and depth cuts. But a full pass divides L₁ by exactly 64, so the end's L₁ is the last pass start's divided by a power of 64, and on those eight it falls in short intervals that hold no value ≡ 10 (mod 14), the residue of L₁ at every pass start, other than −4, which pass_clean8 excludes (untrusted, runs/end_l1.py). So no route or path found so far is left above the floor. An untrusted count of every pass start up to width 2⁷⁴ of the loop's chains from the loop entries of the 36- and 40-digit trees (the 169,631 entry classes at 40 digits give 193,243 classes of one coordinate, none more than five steps from its entry) meets neither lane at any lane value either, a second check for those entries only: in a sample of the blank-tape run, 3 of 26,961 first entries above 2⁴¹ lie in none of the 40-digit classes, and since the cut classes keep their number at every depth, no finite count covers every entry. So, on the exhaustive search, what the censuses leave is the routes they have not found, and the family of lanes below.
The lanes of the six routes and the two new lanes belong to one family of lanes that goes on without end: before it re-enters, the run makes no pass of a loop on four walls on the six routes' lanes, one on the two new lanes, and one more on each later pair. Each pass raises by about 12 bits the width up to which R′³/L₁′² leaves a lane's paths, on the paths since followed on the next pair and on one path on each of three lanes further out, with three to five passes. So at the 2⁶⁶ floor the paths on the next pair are left against any end below 178, up to width 278.1, and the three further out against a close as well, with the narrower classes the theorems take, up to 275.1, 287.1 and 299.1 (with the wider ones up to 277.7, 289.7 and 2101.7, and two on the next pair's second lane up to 267.7); the end's own L₁, or the close's, does not rule them out either, and no floor closes the family (untrusted, the same scripts). On the next pair, a census on the halting side of the lines of pass starts, each with a fixed R and L₁, that those paths' ends would need (89 lines, and two more for the two closes) finds no halt or close on any of them, only clean tapes and depth cuts: evidence, not proof (untrusted). The count above takes in every lane of the family at once: up to width 2²⁵⁶ the chains from the 40-digit entries meet the family 112 times and the other census lanes 4 times, and from the entry of each the run goes on to the next clean tape within 21 rounds (untrusted). For those entries that leaves only lanes far out in the family, which the filter leaves above 2²⁵⁶.
The far shape does not keep the family off either: pass starts that meet every condition on the pass start and halt are proved on the first new lane, with one pass (lane769_far_wide), and on the lanes with two to five passes, wider than 2⁶⁶ from three passes on, within the widths the filter leaves there (loop3_far_66, loop4_far_66, loop5_far_66, above). Nor does a bound on the shape of the kind the run's own pass starts show: the search that found those members finds members in the region of the run's first loop entries and in the window a full pass lands in (untrusted, against the run's data to 2⁴³, below). Above the 2⁶⁶ floor and within the widths the filter leaves there, it finds halting classes on the three-pass lane only at the lane values 2⁶⁴ to 2⁶⁶, none at 2⁶⁷ to 2⁷⁵, but it did not look at the lanes 3 · 2j there or for other routes (untrusted). So for every entry, the family has to be kept off by an argument over the four-wall loop itself, together with what the chain from the run's own loop entries reaches. The lab notes sketch a handle: on each route the halting classes converge 2-adically as the lane value grows, so a class of clean tapes that the clean-tape tree settles, with the chain's last pass start affine in the clean tape, can meet a halting class on the family at only finitely many lane values unless two fixed 2-adic numbers are equal, and what that leaves is the classes the tree cuts at every depth (a sketch, not a proof). Formally, what is open is whether the run reaches a pass start with R ≥ 769 and that shape that halts. Closing it this way needs a proof of the routes' forms and of the exhaustive search or the far-shape search, an argument for the family, and on the halting side every halting class at every R, not a census.
The machine's own run from blank tape, followed in the mark model to width 2⁴³ (2.5 × 10¹² rounds; untrusted, blankrun/), agrees: it passes 1.8 billion pass starts, none in or near one of the eight families and none on the halting lanes of the main route, and no chain from a loop entry lands more than three times. None of the pass starts kept in its data (every one below width 2³⁴, a 1/1024 sample to 2⁴³ and the rarer kinds, 5.6 million rows) lies on a lane of the family above either, and the low binary digits that decide which of the family's lanes a pass start could be on are spread as at random, so they do not keep the run off the family's later lanes. Some pass starts later in a cycle, after the first entry's chain has ended, fail the 15/64 shape, and so does the chain of one first entry, at width 241.4, whose middle wall is only 0.13 of the width from the end. That is no exception to the theorems: the shape is proved for the chains from the loop entries where the tree stops, and the tree stops only at an entry that passes its check. This one fails it, so the tree follows the run past it, here to the next clean tape.
Halts by re-entry get rarer at larger scales: on the main route the new halving chain reaches 0 only from an end meeting at 2j − 2, which takes W − b of about 2j+2, and then only when the middle wall lies in one class modulo about 21.5j + 2, about 1.5 binary digits per halving (an untrusted symbolic search, for j from 10 to 32). In random samples, where W − b is of the order of the width, 9 of 50 million starts with R ≥ 178 closed this way at width about 2¹¹, and none of 25 million each at 2²⁰, 2³⁰ and 2⁴¹.
At the depths measured, the open part of the tree for R ≥ 178 is all where the depth ran out, none at a round decided as a halt, and it shrinks with depth: 8.8%, 3.8% and 1.6% of a class at 16, 20 and 24 splits. Run on the points where a full pass can land, the tree leaves as much open (8.6% at 16 splits; untrusted). From a loop entry, the pass starts the run reaches form a family of one coordinate, the clean tape's own class, and every landing of the loop lies on one plane, 2(b − a) = W − 2R − 6 (proved, landing_plane). Followed in that coordinate, the part of the entries' measure still open falls from 13.5% at 8 more splits to 4.6% at 12 and 1.5% at 16 (over the 1,845 entries at 28 digits; ReachStats.lean, an untrusted survey).
Not the way forward: a lock for the extra-wall loops. With extra walls the loop has other passes. The detour Q has a never-zero quadratic countdown, and so does every periodic word in the passes P and Q up to length 12, but mixtures have none. And the open cases hardly use these loops: only 0.09% of the 1,255,963 clean-tape classes that both trees leave open at 36 digits ever meet the extra-wall pass start, and under 1% of the pass-start trees' open measure at 20 splits (a survey of the trees the proved explorers build, not a proof). So no lock for these loops can settle either case.
Heuristic odds of a halt beyond the exhaustive range are tiny (of order 10⁻³² or less), but they are estimates from measured rates, not proof. The summary page grades every statement as proved, checked, measured or heuristic.
How to check it
The proofs use Lean 4.34.0 with the core library only (no Mathlib, no Lake). scripts/setup-lean.sh installs it to /opt/lean-4.34.0 (it needs root, for /opt and /etc/profile.d). Times below are on 4 cores.
git clone https://github.com/fractal-geometry-explorer/busy-beaver-explorer
cd busy-beaver-explorer
sudo scripts/setup-lean.sh && . /etc/profile.d/lean.sh
cd bb6-holdout/lean
./check.sh # the BB6 modules: rules, rounds, trees, explorers (about a minute)
./check_end.sh # every theorem file, kernel and native pieces (about 24 minutes)
./check_end.sh --deep # also the 40-digit measures (about 39 minutes)
./check_end.sh --deep --deeper # and the 44-digit measure (about 71 minutes)
./check_route.sh --fast # the route tree at every depth, and its 36-digit measure
Each theorem file ends with #print axioms. For blank_halt_open_far_kernel, as for the other kernel-only theorems, it should list only propext, Classical.choice and Quot.sound; for blank_halt_open_big it also lists what native_decide adds for the two evaluated checks, prefix_ok and clean_direct_ok. The certificates check in Python with exact arithmetic:
cd bb6-holdout/cert && gunzip -k *.gz
python3 check_endgame.py endgame_leaves.txt
python3 check_exit.py exit_leaves.txt
python3 check_tree.py tree36_leaves.txt # hours
The exhaustive search is about 80 CPU hours to 60 digits, split into 384 parts by dfs/run_parts.sh and merged with dfs/merge.py; compare the result with dfs/merged60_fixed.txt. To 64 digits it is about 420 CPU hours with csearch/nrefdfs2w.c in 1536 parts at split level 33; compare with dfs/merged64.txt.
The statement of blank_halt_open_big in Lean
theorem blank_halt_open_big (T : Nat) (hT : steps T ⟨blank, blank, .A⟩ = none) :
∃ W k, directWidth ≤ W ∧ W % 2 = 0 ∧ (∀ d, (cleanTreeG directWidth d).cutMem [(W : Int) / 2, 0] = true) ∧
steps k ⟨blank, blank, .A⟩ = some (roundStart [⟨.M, W - 2⟩] W) ∧
steps (T - k) (roundStart [⟨.M, W - 2⟩] W) = none ∧
(((∀ d, (cleanTreeGB directWidth d).cutMem [(W : Int) / 2, 0] = true) ∧
∃ u, Reach ⟨[], 1, [⟨.M, W - 2⟩], W⟩ u ∧ u.wf ∧ (EndClose u ∨ InteriorContact u)) ∨
∃ R a b W₁ t, W < W₁ ∧ 769 ≤ R ∧ 15 * W₁ ≤ 64 * (W₁ - b) ∧
PassStart448 [⟨.W, a⟩, ⟨.W, b⟩, ⟨.W, W₁ - R - 1⟩] W₁ R ∧
(∀ d, (passTreeSym d).cutMem [((a : Int) - 1) / 2, (b : Int) / 2, (W₁ : Int) / 2, (R : Int) / 2] = true) ∧
steps t (roundStart [⟨.M, W - 2⟩] W) = some (roundStart [⟨.W, a⟩, ⟨.W, b⟩, ⟨.W, W₁ - R - 1⟩] W₁) ∧
steps (T - k - t) (roundStart [⟨.W, a⟩, ⟨.W, b⟩, ⟨.W, W₁ - R - 1⟩] W₁) = none ∧
∃ u, Reach ⟨[], 1, [⟨.W, a⟩, ⟨.W, b⟩, ⟨.W, W₁ - R - 1⟩], W₁⟩ u ∧ u.wf ∧
(EndClose u ∨ InteriorContact u))
Here directWidth = 2⁴¹, steps is the machine itself (none means halted), roundStart is the tape of a mark state, cleanTreeG is the plain clean-tape tree, cleanTreeGB the one that stops at checked loop entries, and passTreeSym the pass-start tree for R ≥ 178.