Cook–Levin machines: inertia literal block
ProvedCookLevin.machine_emit_inertia_literal_blockcomplexitycook-levinloopsturing-machines
For each fixed symbol bound, emit the actual positive-head, negative-current-cell, positive-next-time-cell inertia clauses for every symbol at one tableau position. Three canonical unary counters supply the literal bases. All counters and work tapes are preserved, and the runtime is affine in the sum of the counters. Zero symbols are allowed.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_inertia_literal_block {k G : Nat} (hk : 5 ≤ k) (hG : 4 ≤ G)
(symbols : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t j p : Nat) (input : Tape) (bits : List Bool) (saved : List Tape),
sh.G = symbols → saved.length + 5 = k →
let a := literalN (.Pos (sh.headVar t j p))
let b := literalN (.Neg (sh.cellVar t j p blankSymbol))
let c := literalN (.Pos (sh.cellVar (t + 1) j p blankSymbol))
let chunk := (encodeFormula ((List.range sh.G).map fun s =>
[Literal.Pos (sh.headVar t j p), 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 true)), 1 + b) ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: saved) (A * (a + b + c) + 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 (bits ++ chunk)), 1 + (bits ++ chunk).length) :: saved) := by sorrySource
Compose the three-counter template compiler, fixed counter strides and reusable unary iteration with the actual inertia-clause encoding.