Cook–Levin machines: compile clauses with three unary offsets
ProvedCookLevin.machine_emit_three_counter_templatecomplexitycook-levinloopsturing-machines
Every fixed clause template with literal values selected from three runtime unary counters plus fixed offsets has a well-formed emitting machine. It appends the encoded clause block without its formula terminator, preserves the counters, input and work tapes, and runs in A*(a+b+c)+B steps for constants depending only on the template.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_three_counter_template {k G : Nat} (hk : 5 ≤ k) (hG : 4 ≤ G)
(φ : List (List (Fin 3 × Nat))) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (a b c : Nat) (input : Tape) (bits : List Bool) (saved : List Tape),
saved.length + 5 = k →
let chunk := φ.flatMap fun ns => true :: encodeListNat
(ns.map fun x => (if x.1.val = 0 then a else if x.1.val = 1 then b else c) + x.2)
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
Induct over the fixed clauses and literals, composing fixed-bit writers with the accepted three-counter appender.