K230: the 230-state Turing machine
DefinitionK230_tmThe frozen binary Turing machine K230: its 230-row transition table table230 (state 230 is the halt state with no row), the transition function tmn, and the halting semantics on a bi-infinite binary tape. Halts c0 means the machine started in state 0 on the all-zero tape eventually reaches a halting configuration. Ports Table230.v, TM230.v, and BusyCoq's TM.v specialized to Ctx230.
Definition code
namespace K230
inductive Dir where | L | R
deriving DecidableEq, Repr
def table230 : List (Bool × Dir × Nat × Bool × Dir × Nat) := [
(true, .R, 94, true, .R, 0),
(false, .L, 1, true, .L, 2),
(false, .L, 3, true, .L, 2),
(false, .L, 5, true, .L, 2),
(true, .R, 6, false, .L, 4),
(false, .L, 9, true, .L, 2),
(false, .R, 6, false, .R, 10),
(false, .R, 11, true, .R, 12),
(false, .R, 14, true, .R, 13),
(false, .L, 15, true, .L, 2),
(false, .L, 16, false, .R, 10),
(false, .L, 26, true, .R, 18),
(false, .R, 19, true, .R, 20),
(false, .L, 91, true, .L, 31),
(false, .L, 11, false, .R, 22),
(false, .L, 23, true, .L, 2),
(true, .L, 1, false, .L, 1),
(false, .R, 24, false, .R, 32),
(false, .R, 26, false, .L, 27),
(false, .R, 28, true, .R, 29),
(false, .R, 30, true, .R, 31),
(false, .R, 24, false, .R, 60),
(false, .R, 33, true, .R, 22),
(false, .L, 34, true, .L, 2),
(false, .L, 35, false, .R, 0),
(false, .R, 36, true, .R, 25),
(false, .R, 37, true, .R, 38),
(false, .R, 39, false, .L, 40),
(false, .R, 41, true, .R, 42),
(false, .R, 43, true, .R, 44),
(false, .R, 45, true, .R, 46),
(false, .R, 21, true, .R, 47),
(false, .R, 48, true, .R, 32),
(false, .R, 32, true, .R, 33),
(false, .L, 50, true, .L, 2),
(true, .R, 35, true, .L, 1),
(false, .R, 51, true, .R, 36),
(false, .R, 17, true, .R, 52),
(false, .R, 13, true, .R, 53),
(false, .L, 11, false, .R, 36),
(false, .L, 4, true, .L, 54),
(false, .R, 24, false, .R, 25),
(false, .R, 13, false, .L, 16),
(false, .R, 56, true, .R, 57),
(false, .R, 58, true, .R, 59),
(false, .R, 24, false, .R, 55),
(false, .R, 61, true, .R, 62),
(false, .R, 63, false, .L, 16),
(false, .R, 25, true, .R, 48),
(false, .L, 35, false, .R, 64),
(false, .L, 75, true, .L, 2),
(false, .R, 16, true, .R, 51),
(false, .R, 67, false, .L, 27),
(false, .R, 68, true, .R, 69),
(false, .L, 40, true, .L, 54),
(false, .R, 22, true, .R, 55),
(false, .L, 11, false, .R, 51),
(false, .R, 61, false, .L, 16),
(false, .R, 70, true, .R, 71),
(false, .R, 62, true, .R, 72),
(false, .R, 55, true, .R, 60),
(false, .R, 49, false, .R, 25),
(false, .L, 28, true, .L, 73),
(false, .R, 49, false, .R, 55),
(false, .R, 74, true, .R, 64),
(false, .R, 114, true, .R, 12),
(true, .R, 198, true, .L, 54),
(false, .R, 76, true, .R, 229),
(false, .R, 77, true, .R, 230),
(false, .L, 78, true, .R, 31),
(false, .R, 41, true, .R, 79),
(false, .R, 21, true, .R, 80),
(false, .R, 56, true, .L, 81),
(false, .R, 82, true, .R, 83),
(true, .R, 0, true, .R, 64),
(false, .R, 75, true, .R, 84),
(false, .R, 85, true, .R, 86),
(false, .R, 87, true, .R, 88),
(false, .R, 89, true, .R, 90),
(false, .R, 82, true, .R, 62),
(false, .R, 91, false, .L, 42),
(false, .L, 92, true, .R, 57),
(false, .R, 49, false, .R, 33),
(false, .R, 93, false, .L, 42),
(false, .R, 95, true, .R, 96),
(false, .R, 19, true, .R, 65),
(false, .R, 90, true, .R, 99),
(false, .R, 21, true, .R, 102),
(false, .R, 45, true, .R, 103),
(false, .R, 104, true, .R, 81),
(false, .R, 105, true, .R, 106),
(false, .R, 82, true, .R, 81),
(false, .R, 104, true, .R, 107),
(false, .R, 108, true, .R, 109),
(false, .R, 66, false, .R, 0),
(false, .R, 27, true, .R, 110),
(false, .R, 111, true, .R, 112),
(true, .L, 113, true, .L, 97),
(false, .R, 19, true, .R, 114),
(false, .R, 61, true, .R, 61),
(false, .R, 153, true, .R, 116),
(false, .R, 153, true, .R, 170),
(false, .R, 120, true, .R, 121),
(false, .R, 122, false, .L, 52),
(false, .R, 123, true, .R, 124),
(false, .R, 72, true, .R, 59),
(false, .R, 58, true, .R, 125),
(false, .R, 21, true, .R, 126),
(false, .R, 21, false, .L, 40),
(false, .R, 62, true, .R, 42),
(false, .R, 127, true, .R, 8),
(false, .R, 104, true, .R, 128),
(false, .R, 92, true, .R, 129),
(false, .L, 40, false, .L, 97),
(false, .R, 130, true, .R, 107),
(false, .R, 69, true, .R, 131),
(false, .R, 172, true, .R, 192),
(false, .R, 186, true, .R, 173),
(false, .R, 155, true, .R, 173),
(false, .R, 152, true, .R, 101),
(false, .R, 45, false, .L, 10),
(false, .R, 31, true, .R, 63),
(false, .L, 137, false, .L, 1),
(false, .R, 39, true, .R, 73),
(false, .R, 62, true, .R, 138),
(false, .R, 62, true, .R, 139),
(false, .R, 140, false, .L, 16),
(false, .R, 14, true, .R, 138),
(false, .R, 21, true, .R, 141),
(false, .R, 142, true, .R, 143),
(false, .R, 144, true, .L, 20),
(false, .R, 145, true, .R, 146),
(false, .R, 147, true, .L, 163),
(false, .R, 76, true, .R, 187),
(false, .R, 182, true, .R, 183),
(false, .R, 191, true, .R, 100),
(false, .R, 12, true, .R, 117),
(false, .R, 30, true, .R, 70),
(false, .R, 39, true, .L, 130),
(false, .R, 160, false, .L, 16),
(false, .R, 49, false, .R, 48),
(false, .R, 161, false, .L, 16),
(false, .R, 17, true, .R, 162),
(false, .R, 163, true, .R, 164),
(false, .R, 24, false, .R, 48),
(false, .R, 165, true, .R, 78),
(false, .R, 98, true, .R, 90),
(false, .R, 98, true, .R, 166),
(false, .R, 136, true, .R, 154),
(false, .R, 12, true, .R, 166),
(false, .R, 90, true, .R, 90),
(false, .R, 90, true, .R, 168),
(false, .R, 155, true, .R, 171),
(false, .R, 86, true, .L, 172),
(false, .R, 158, true, .R, 171),
(false, .R, 85, true, .R, 175),
(false, .R, 171, true, .R, 176),
(false, .R, 90, true, .R, 86),
(false, .R, 177, true, .R, 176),
(false, .R, 166, true, .R, 118),
(false, .R, 99, true, .R, 99),
(false, .R, 49, false, .R, 32),
(false, .R, 7, false, .L, 27),
(false, .R, 146, true, .R, 28),
(false, .R, 77, true, .R, 98),
(false, .R, 166, true, .R, 19),
(false, .R, 19, true, .R, 179),
(false, .R, 172, true, .R, 180),
(false, .R, 177, true, .R, 181),
(false, .R, 99, true, .R, 148),
(false, .R, 169, true, .R, 157),
(false, .R, 183, true, .R, 149),
(false, .R, 184, true, .R, 185),
(false, .R, 153, true, .R, 182),
(false, .R, 151, true, .R, 119),
(false, .L, 76, true, .R, 61),
(false, .R, 188, true, .R, 175),
(false, .R, 166, true, .R, 188),
(false, .R, 189, true, .R, 189),
(false, .R, 194, true, .R, 128),
(false, .R, 184, true, .R, 153),
(false, .R, 99, true, .R, 176),
(false, .R, 76, true, .R, 61),
(false, .R, 150, true, .R, 98),
(false, .R, 175, true, .R, 90),
(false, .R, 90, true, .R, 184),
(false, .R, 147, true, .R, 86),
(false, .R, 186, true, .R, 183),
(false, .L, 131, true, .L, 190),
(false, .R, 149, true, .L, 156),
(false, .R, 12, true, .R, 189),
(false, .R, 166, true, .R, 182),
(false, .R, 172, true, .R, 194),
(false, .R, 195, true, .R, 196),
(false, .R, 17, true, .L, 137),
(false, .R, 196, true, .R, 197),
(false, .R, 77, true, .R, 122),
(false, .R, 109, true, .R, 130),
(true, .L, 198, true, .L, 113),
(false, .R, 180, true, .R, 166),
(false, .R, 157, true, .R, 167),
(false, .R, 149, true, .R, 150),
(false, .R, 201, true, .R, 151),
(false, .R, 132, true, .R, 202),
(false, .R, 115, true, .R, 203),
(false, .R, 99, true, .R, 134),
(false, .R, 186, true, .R, 199),
(false, .R, 205, true, .R, 206),
(false, .R, 182, true, .R, 199),
(false, .R, 133, true, .R, 208),
(false, .R, 174, true, .R, 209),
(false, .R, 207, true, .R, 210),
(false, .R, 166, true, .R, 189),
(false, .R, 190, true, .R, 147),
(false, .R, 90, true, .R, 213),
(false, .R, 147, true, .R, 158),
(false, .R, 157, true, .R, 178),
(false, .R, 216, true, .R, 167),
(false, .R, 215, true, .R, 217),
(false, .R, 214, true, .R, 218),
(false, .R, 200, true, .R, 200),
(false, .R, 157, true, .R, 220),
(false, .R, 219, true, .R, 221),
(false, .R, 212, true, .R, 222),
(false, .R, 155, true, .R, 159),
(false, .R, 135, true, .R, 193),
(false, .R, 224, true, .R, 225),
(false, .R, 223, true, .R, 226),
(false, .R, 211, true, .R, 227),
(false, .R, 204, true, .R, 228)
]
def tmNth {α : Type} : List α → Nat → Option α
| [], _ => none
| a :: _, 0 => some a
| _ :: l, n + 1 => tmNth l n
def tmn (q : Nat) (s : Bool) : Option (Bool × Dir × Nat) :=
match tmNth table230 q with
| none => none
| some (w0, d0, n0, w1, d1, n1) => if s then some (w1, d1, n1) else some (w0, d0, n0)
def Tape := Int → Bool
def Config := Nat × Tape × Int
def headSym (c : Config) : Bool := c.2.1 c.2.2
def writeTape (t : Tape) (pos : Int) (w : Bool) : Tape := fun i => if i = pos then w else t i
def Halted (c : Config) : Prop := tmn c.1 (headSym c) = none
inductive Step : Config → Config → Prop where
| mk (q : Nat) (t : Tape) (pos : Int) (w : Bool) (d : Dir) (q' : Nat) :
tmn q (t pos) = some (w, d, q') → Step (q, t, pos) (q', writeTape t pos w, if d = Dir.R then pos + 1 else pos - 1)
inductive Steps : Nat → Config → Config → Prop where
| zero (c : Config) : Steps 0 c c
| succ (n : Nat) (c c' c'' : Config) : Step c c' → Steps n c' c'' → Steps (n + 1) c c''
def c0 : Config := (0, (fun _ => false), 0)
def Halts (c : Config) : Prop := ∃ n ch, Steps n c ch ∧ Halted ch
end K230Source