Cook–Levin machines: halt tape block
ProvedCookLevin.machine_emit_halt_tape_blockcomplexitycook-levinloopsturing-machines
Emit every halt head/cell constraint on one logical tape. Restore position fuel and advance all four position counters across the unused radix entry to position zero on the next logical tape, with an explicit runtime bound.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_halt_tape_block {k G : Nat} (hk : 8 ≤ k) (hG : 4 ≤ G)
(symbols : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t j : Nat) (input : Tape) (bits : List Bool)
(fuel : Nat → Symbol) (saved : List Tape),
sh.G = symbols → saved.length + 8 = k →
fuel 0 ≠ oneSymbol →
(∀ i, i < sh.T + 1 → fuel (1 + i) = oneSymbol) →
fuel (1 + (sh.T + 1)) ≠ oneSymbol →
let a := literalN (.Neg (sh.stateVar t sh.Q))
let b := fun j => literalN (.Neg (sh.headVar t j 0))
let c := fun j => literalN (.Pos (sh.headVar (t + 1) j 0))
let d := fun j => literalN (.Neg (sh.cellVar t j 0 blankSymbol))
let e := fun j => literalN (.Pos (sh.cellVar (t + 1) j 0 blankSymbol))
let chunk := (List.range (sh.T + 1)).flatMap fun p =>
(encodeFormula ([Literal.Neg (sh.stateVar t sh.Q), Literal.Neg (sh.headVar t j p),
Literal.Pos (sh.headVar (t + 1) j p)] :: (List.range sh.G).map fun s =>
[Literal.Neg (sh.stateVar t sh.Q), Literal.Neg (sh.cellVar t j p s),
Literal.Pos (sh.cellVar (t + 1) j p s)])).dropLast
Transforms R
(input ::
(contents (boolsToSymbols (List.replicate (a) true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate (b (j)) true)), 1 + b (j)) ::
(contents (boolsToSymbols (List.replicate (c (j)) true)), 1 + c (j)) ::
(contents (boolsToSymbols (List.replicate (d (j)) true)), 1 + d (j)) ::
(contents (boolsToSymbols (List.replicate (e (j)) true)), 1 + e (j)) ::
(contents (boolsToSymbols (bits)), 1 + (bits).length) ::
(fuel, 1) ::
saved)
((sh.T + 1) * (A * (a + b (j + 1) + c (j + 1) + d (j + 1) + e (j + 1)) + B + 6) + 4 + (16 + 16 * symbols))
(input ::
(contents (boolsToSymbols (List.replicate (a) true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate (b (j + 1)) true)), 1 + b (j + 1)) ::
(contents (boolsToSymbols (List.replicate (c (j + 1)) true)), 1 + c (j + 1)) ::
(contents (boolsToSymbols (List.replicate (d (j + 1)) true)), 1 + d (j + 1)) ::
(contents (boolsToSymbols (List.replicate (e (j + 1)) true)), 1 + e (j + 1)) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
(fuel, 1) ::
saved) := by sorrySource
Compose the five-counter template compiler, fixed counter strides and reusable unary iteration with the actual halt-clause encoding.