Cook–Levin machines: runtime head-position exclusion row
ProvedCookLevin.machine_emit_head_pair_rowcomplexitycook-levinloopsturing-machines
Emit all ordered head-position exclusion clauses with first position p and second position below runtime n, skipping the diagonal. Restore the unary position fuel and advance the inner counter to position n. Track the last equality flag, including the empty row. Runtime n*(A*(a+b(n)+c)+B+6)+4.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_head_pair_row {k G : Nat} (hk : 7 ≤ k) (hG : 4 ≤ G) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t j p n c : Nat) (input : Tape) (bits : List Bool)
(flag fuel : Nat → Symbol) (saved : List Tape),
saved.length + 7 = k →
fuel 0 ≠ oneSymbol →
(∀ i, i < n → fuel (1 + i) = oneSymbol) →
fuel (1 + n) ≠ oneSymbol →
let a := literalN (.Neg (sh.headVar t j p))
let b := fun q => literalN (.Neg (sh.headVar t j q))
let chunk := (List.range n).flatMap fun q => if p = q then [] else
(encodeFormula [[Literal.Neg (sh.headVar t j p), Literal.Neg (sh.headVar t j q)]]).dropLast
Transforms R
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate (b 0) true)), 1 + b 0) ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: (flag, 1) :: (fuel, 1) :: saved)
(n * (A * (a + b n + c) + B + 6) + 4)
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate (b n) true)), 1 + b n) ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
((fun i => if n = 0 then flag i else
if i = 1 then boolSym (decide (p = n - 1)) else flag i), 1) :: (fuel, 1) :: saved) := by sorrySource
Runtime-sized distinct-position filtering for the Cook–Levin head constraints.