Cook–Levin machines: exact runtime exactly-one head encoding
ProvedCookLevin.machine_emit_head_exactly_onecomplexitycook-levinloopsturing-machines
Emit precisely encodeFormula(exactlyOneOf(range n)(headVar t j)), excluding its final formula terminator. The positive clause precedes every ordered off-diagonal exclusion. Preserve both reusable position fuels and track all three literal counters and the equality flag 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_head_exactly_one {k G : Nat} (hk : 8 ≤ k) (hG : 4 ≤ G) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t j n : Nat) (input : Tape) (bits : List Bool)
(flag inner outer : Nat → Symbol) (saved : List Tape),
saved.length + 8 = k →
inner 0 ≠ oneSymbol → outer 0 ≠ oneSymbol →
(∀ i, i < n → inner (1 + i) = oneSymbol) →
(∀ i, i < n → outer (1 + i) = oneSymbol) →
inner (1 + n) ≠ oneSymbol → outer (1 + n) ≠ oneSymbol →
let a := fun p => literalN (.Neg (sh.headVar t j p))
let c := fun p => literalN (.Pos (sh.headVar t j p))
let chunk := (encodeFormula (exactlyOneOf (List.range n) (sh.headVar t j))).dropLast
Transforms R
(input :: (contents (boolsToSymbols (List.replicate (a 0) true)), 1 + a 0) ::
(contents (boolsToSymbols (List.replicate (a 0) true)), 1 + a 0) ::
(contents (boolsToSymbols (List.replicate (c 0) true)), 1 + c 0) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: (flag, 1) :: (inner, 1) :: (outer, 1) :: saved)
(n * (2 * c n + 19) + 6 + (n * (n * (A * (a n + a n + c n) + B + 28) + 22) + 4))
(input :: (contents (boolsToSymbols (List.replicate (a n) true)), 1 + a n) ::
(contents (boolsToSymbols (List.replicate (a 0) true)), 1 + a 0) ::
(contents (boolsToSymbols (List.replicate (c n) true)), 1 + c n) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
((fun i => if n = 0 then flag i else if i = 1 then oneSymbol else flag i), 1) ::
(inner, 1) :: (outer, 1) :: saved) := by sorrySource
Runtime-sized distinct-position filtering for the Cook–Levin head constraints.