Formalize $BB(5)=47\,176\,870$ in Lean 4 (the 5-state, 2-symbol busy beaver value)
Statement
Prove in Lean 4 the theorem (currently a `sorry` in google-deepmind/formal-conjectures): ``` theorem BB_5 : BB 5 = 47176870 ``` where `BB n := sSup { N | ∃ C : Candidate n, C.M.haltingNumber = N }` is the maximum halting time (max-shift function) over all $n$-state, $2$-symbol Turing machines started on a blank tape (the repo's `Candidate n` bundles such a halting machine). Meaning: the 5-state busy-beaver (maximum-shifts) number is exactly $47176870$.
Acceptance. SUCCESS: a Lean 4 proof replacing the `sorry` that type-checks against a pinned mathlib toolchain, with `#print axioms <thm>` reported and showing NO `sorryAx` (no remaining gaps). Both the $\ge$ (exhibit the champion) and $\le$ (all others) sides of the `sSup` must be established. DISCLOSURE: this is an enormous computational certificate — a `native_decide`/reflection-heavy proof almost certainly enlarges the TCB (`Lean.ofReduceBool`, `Lean.trustCompiler`) and MUST be disclosed; a pure-kernel proof would be a landmark. PARTIAL credit: formalizing `BB_1..BB_4` (values $1,6,21,107$), or the lower bound `47176870 ≤ BB 5` alone via the known champion machine.
Background
$BB(5)=47{,}176{,}870$ was settled by the collaborative Busy Beaver Challenge (bbchallenge.org) and announced in 2024, accompanied by a machine-checked Coq proof — the first new busy-beaver value determined in decades. There is no Lean/mathlib proof. Source: formal-conjectures `FormalConjectures/Wikipedia/BusyBeaver.lean`, declaration `BB_5`, category `research solved`, body `sorry` (commit 3cc3d454f4). Proving it requires both a lower bound (the champion machine runs $47176870$ steps then halts) and an upper bound (every other 5-state machine either halts sooner or never halts).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | formal-conjectures: BusyBeaver.lean (BB_5, sorry) | link |
| REF-02 | The Busy Beaver Challenge (BB(5) determination, 2024) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.