Champion halts in 47,176,870 steps
OpenBB5.champion_haltsThe 5-state champion machine of Figure 1, started on the all-zero tape in the first state, halts after exactly steps, with the final halting transition included in the count.
import Mathlib import Definitions.Def_FCP_BusyBeaver import Definitions.Def_BB5_winner
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 BB5Read-back
What the Lean code literally says, in plain math · claude-opus-6
This theorem, closed by sorry, asserts . Here winner is the concrete 5-state machine with transition table , , , , , , , , , , with states , meaning false/blank and meaning true, R/L the direction Boolean, and halt the none next state. The argument is the all-blank start configuration (state , head at integer position , tape identically ); by omega discharges the arithmetic proof of that init requires to build state index . Unfolding , the assertion is with 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 and halted after exactly transitions, so the halting transition is the -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 the universal clause is non-vacuous. The declaration is closed by sorry.