Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

5-state Busy Beaver winner (Figure 1)

Definition
BB5_winner

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

computabilitycomputer-assistedturing-machines

The concrete 5-state, 2-symbol Turing machine discovered by Marxen and Buntrock in 1989, given in the paper as 1RB1LC_1RC1RB_1RD0LE_1LA1LD_---0LA. It halts after 47,176,870 steps from the all-zero tape and is the champion witnessing the lower bound on S(5)S(5)S(5). States AAA–EEE are encoded as 000–444, symbol 000 as false and 111 as true, moves Right/Left as true/false, and an undefined (halting) transition as none.

Definition code
import Mathlib
import Definitions.Def_FCP_BusyBeaver

namespace BB5

/-- The 5-state 2-symbol Busy Beaver winner discovered by Marxen and Buntrock (1989),
given in linear form `1RB1LC_1RC1RB_1RD0LE_1LA1LD_---0LA` (paper Figure 1(a)).
States A,B,C,D,E are encoded as 0,1,2,3,4; symbol `false` is 0 and `true` is 1;
a move direction `true` is Right and `false` is Left; `none` is an undefined
transition, i.e. the machine halts. -/
def winner : FCP.BusyBeaver.TM 5 where
  trans
    | 0, false => (true, true, some 1)    -- A,0 -> 1 R B
    | 0, true  => (true, false, some 2)   -- A,1 -> 1 L C
    | 1, false => (true, true, some 2)    -- B,0 -> 1 R C
    | 1, true  => (true, true, some 1)    -- B,1 -> 1 R B
    | 2, false => (true, true, some 3)    -- C,0 -> 1 R D
    | 2, true  => (false, false, some 4)  -- C,1 -> 0 L E
    | 3, false => (true, false, some 0)   -- D,0 -> 1 L A
    | 3, true  => (true, false, some 3)   -- D,1 -> 1 L D
    | 4, false => (false, false, none)    -- E,0 -> --- (halt)
    | 4, true  => (false, false, some 0)  -- E,1 -> 0 L A

end BB5
Source
arXiv:2509.12337, https://arxiv.org/abs/2509.12337, Figure 1(a)
Read-back

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

One declaration introduces a single concrete object, winner, whose type is that of 5-state, 2-symbol Turing machines as formalized in this bundle. In general such a machine (a TM n) is just a transition function with domain Fin n×{false,true}\mathrm{Fin}\,n \times \{\mathrm{false},\mathrm{true}\}Finn×{false,true}, i.e. one entry for each of the nnn states (labelled 0,…,n−10,\dots,n-10,…,n−1) and each of the two tape symbols, where each entry is a triple (written symbol, direction, next state-or-halt). For winner specifically n=5n=5n=5; the state labels used here are A=0,B=1,C=2,D=3,E=4A=0,B=1,C=2,D=3,E=4A=0,B=1,C=2,D=3,E=4, the symbol Boolean is interpreted as 000 for false (blank) and 111 for true, the direction Boolean is interpreted as Right for true and Left for false, and the "halt" outcome is the none value of the optional next-state field. The transition function is fixed to the table read as δ(state,read)=(write,move,next)\delta(\text{state},\text{read})=(\text{write},\text{move},\text{next})δ(state,read)=(write,move,next): (A,0)↦(1,R,B)(A,0)\mapsto(1,R,B)(A,0)↦(1,R,B), (A,1)↦(1,L,C)(A,1)\mapsto(1,L,C)(A,1)↦(1,L,C), (B,0)↦(1,R,C)(B,0)\mapsto(1,R,C)(B,0)↦(1,R,C), (B,1)↦(1,R,B)(B,1)\mapsto(1,R,B)(B,1)↦(1,R,B), (C,0)↦(1,R,D)(C,0)\mapsto(1,R,D)(C,0)↦(1,R,D), (C,1)↦(0,L,E)(C,1)\mapsto(0,L,E)(C,1)↦(0,L,E), (D,0)↦(1,L,A)(D,0)\mapsto(1,L,A)(D,0)↦(1,L,A), (D,1)↦(1,L,D)(D,1)\mapsto(1,L,D)(D,1)↦(1,L,D), (E,0)↦halt(E,0)\mapsto\text{halt}(E,0)↦halt, (E,1)↦(0,L,A)(E,1)\mapsto(0,L,A)(E,1)↦(0,L,A). Fine print: on the halting entry (E,0)(E,0)(E,0) the written symbol and direction are stored in the table but discarded by the step operation, because whenever the next-state field is none the step returns "halted" with no write and no head movement; they take effect only on non-halting entries. This declaration only pins down the transition function; it asserts no initial configuration, no halting claim, and no maximality claim.

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