5-state Busy Beaver winner (Figure 1)
DefinitionBB5_winnerThe 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 . States – are encoded as –, symbol as false and as true, moves Right/Left as true/false, and an undefined (halting) transition as none.
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 BB5Read-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 , i.e. one entry for each of the states (labelled ) and each of the two tape symbols, where each entry is a triple (written symbol, direction, next state-or-halt). For winner specifically ; the state labels used here are , the symbol Boolean is interpreted as for false (blank) and 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 : , , , , , , , , , . Fine print: on the halting entry 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.