Cook–Levin machines: halt tapes block
ProvedCookLevin.machine_emit_halt_tapes_blockcomplexitycook-levinloopsturing-machines
Emit every halt head/cell constraint over all logical tapes at one time. Restore position fuel and advance all four spatial counters to the next time, 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_tapes_block {k G : Nat} (hk : 8 ≤ k) (hG : 4 ≤ G)
(tapes symbols : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t : Nat) (input : Tape) (bits : List Bool)
(fuel : Nat → Symbol) (saved : List Tape),
sh.k = tapes → 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 t => literalN (.Neg (sh.headVar t 0 0))
let c := fun t => literalN (.Pos (sh.headVar (t + 1) 0 0))
let d := fun t => literalN (.Neg (sh.cellVar t 0 0 blankSymbol))
let e := fun t => literalN (.Pos (sh.cellVar (t + 1) 0 0 blankSymbol))
let chunk := (List.range sh.k).flatMap fun j =>
(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 (t)) true)), 1 + b (t)) ::
(contents (boolsToSymbols (List.replicate (c (t)) true)), 1 + c (t)) ::
(contents (boolsToSymbols (List.replicate (d (t)) true)), 1 + d (t)) ::
(contents (boolsToSymbols (List.replicate (e (t)) true)), 1 + e (t)) ::
(contents (boolsToSymbols (bits)), 1 + (bits).length) ::
(fuel, 1) ::
saved)
(tapes * ((sh.T + 1) * (A * (a + b (t + 1) + c (t + 1) + d (t + 1) + e (t + 1)) + B + 6) + 4 + (16 + 16 * symbols)))
(input ::
(contents (boolsToSymbols (List.replicate (a) true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate (b (t + 1)) true)), 1 + b (t + 1)) ::
(contents (boolsToSymbols (List.replicate (c (t + 1)) true)), 1 + c (t + 1)) ::
(contents (boolsToSymbols (List.replicate (d (t + 1)) true)), 1 + d (t + 1)) ::
(contents (boolsToSymbols (List.replicate (e (t + 1)) true)), 1 + e (t + 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.