Cook–Levin machines: halt state literal block
ProvedCookLevin.machine_emit_halt_state_literal_blockcomplexitycook-levinloopsturing-machines
Emit the actual halt state-persistence clause using a fixed literal offset, preserving all five unary counters, with an explicit linear 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_state_literal_block {k G : Nat} (hk : 7 ≤ k) (hG : 4 ≤ G)
(states : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t : Nat) (b c d e : Nat) (input : Tape) (bits : List Bool) (saved : List Tape),
sh.Q = states → saved.length + 7 = k →
let a := literalN (.Neg (sh.stateVar t sh.Q))
let chunk := (encodeFormula [[Literal.Neg (sh.stateVar t sh.Q),
Literal.Pos (sh.stateVar (t + 1) sh.Q)]]).dropLast
Transforms R
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate b true)), 1 + b) ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
(contents (boolsToSymbols (List.replicate d true)), 1 + d) ::
(contents (boolsToSymbols (List.replicate e true)), 1 + e) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: saved) (A * (a + b + c + d + e) + B)
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate b true)), 1 + b) ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
(contents (boolsToSymbols (List.replicate d true)), 1 + d) ::
(contents (boolsToSymbols (List.replicate e true)), 1 + e) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) :: saved) := by sorrySource
Compose the five-counter template compiler, fixed counter strides and reusable unary iteration with the actual halt-clause encoding.