Cook–Levin machines: inertia clause body
ProvedCookLevin.machine_emit_inertia_clause_bodycomplexitycook-levinloopsturing-machines
Emit all actual inertia clauses at one position, then advance the head counter by 8 and both cell counters by 8*symbols. Input, output prefix and saved work are handled exactly; runtime is affine in the three counter values. 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_clause_body {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 + 8) true)), 1 + (a + 8)) ::
(contents (boolsToSymbols (List.replicate (b + 8 * symbols) true)), 1 + (b + 8 * symbols)) ::
(contents (boolsToSymbols (List.replicate (c + 8 * symbols) true)), 1 + (c + 8 * symbols)) ::
(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.