Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Champion halts in 47,176,870 steps

Open
BB5.champion_halts

by loader3229 · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

computabilitycomputer-assistedturing-machines

The 5-state champion machine of Figure 1, started on the all-zero tape in the first state, halts after exactly 47,176,87047{,}176{,}87047,176,870 steps, with the final halting transition included in the count.

Preamble
import Mathlib
import Definitions.Def_FCP_BusyBeaver
import Definitions.Def_BB5_winner
Formal statement
import Mathlib
import Definitions.Def_FCP_BusyBeaver
import Definitions.Def_BB5_winner

namespace BB5

/-- The 5-state champion machine of Figure 1 (Marxen--Buntrock 1989), started
on the all-zero tape in state A, halts after exactly 47,176,870 steps, where the
step count includes the final halting transition (paper Section 2 convention). -/
theorem champion_halts :
    FCP.BusyBeaver.HaltsIn winner (FCP.BusyBeaver.init (by omega)) 47176870 := by
  sorry

end BB5
Source
arXiv:2509.12337, https://arxiv.org/abs/2509.12337, Figure 1 and Section 2
Read-back

What the Lean code literally says, in plain math · claude-opus-6

This theorem, closed by sorry, asserts HaltsIn(winner,init(by omega),47,176,870)\mathrm{HaltsIn}(\mathrm{winner},\mathrm{init}(\texttt{by omega}),47{,}176{,}870)HaltsIn(winner,init(by omega),47,176,870). Here winner is the concrete 5-state machine with transition table δ(A,0)=(1,R,B)\delta(A,0)=(1,R,B)δ(A,0)=(1,R,B), δ(A,1)=(1,L,C)\delta(A,1)=(1,L,C)δ(A,1)=(1,L,C), δ(B,0)=(1,R,C)\delta(B,0)=(1,R,C)δ(B,0)=(1,R,C), δ(B,1)=(1,R,B)\delta(B,1)=(1,R,B)δ(B,1)=(1,R,B), δ(C,0)=(1,R,D)\delta(C,0)=(1,R,D)δ(C,0)=(1,R,D), δ(C,1)=(0,L,E)\delta(C,1)=(0,L,E)δ(C,1)=(0,L,E), δ(D,0)=(1,L,A)\delta(D,0)=(1,L,A)δ(D,0)=(1,L,A), δ(D,1)=(1,L,D)\delta(D,1)=(1,L,D)δ(D,1)=(1,L,D), δ(E,0)=halt\delta(E,0)=\text{halt}δ(E,0)=halt, δ(E,1)=(0,L,A)\delta(E,1)=(0,L,A)δ(E,1)=(0,L,A), with states A=0,…,E=4A=0,\dots,E=4A=0,…,E=4, 000 meaning false/blank and 111 meaning true, R/L the direction Boolean, and halt the none next state. The argument init(by omega)\mathrm{init}(\texttt{by omega})init(by omega) is the all-blank start configuration (state 000, head at integer position 000, tape identically 000); by omega discharges the arithmetic proof of 0<50<50<5 that init requires to build state index 000. Unfolding HaltsIn\mathrm{HaltsIn}HaltsIn, the assertion is run(winner,init,47,176,870)=none ∧ ∀ s<47,176,870, run(winner,init,s)≠none\mathrm{run}(\mathrm{winner},\mathrm{init},47{,}176{,}870)=\mathrm{none}\ \wedge\ \forall\,s<47{,}176{,}870,\ \mathrm{run}(\mathrm{winner},\mathrm{init},s)\neq\mathrm{none}run(winner,init,47,176,870)=none ∧ ∀s<47,176,870, run(winner,init,s)=none with run\mathrm{run}run iterating the single step (halt on a none next-state entry, otherwise write, move one cell right/left per the direction Boolean, and change state). In words: started on the blank tape the machine is in a live configuration after every s<47,176,870s<47{,}176{,}870s<47,176,870 and halted after exactly 47,176,87047{,}176{,}87047,176,870 transitions, so the halting transition is the 47,176,87047{,}176{,}87047,176,870-th and the count includes that final halting step; a halting step returns none without writing or moving, so it is counted but changes neither tape nor head. Since 47,176,870>047{,}176{,}870>047,176,870>0 the universal clause is non-vacuous. The declaration is closed by sorry.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me