Cook–Levin machines: runtime positive head-position clause
ProvedCookLevin.machine_emit_head_positive_clausecomplexitycook-levinloopsturing-machines
Emit the single positive clause listing all head positions below runtime n, excluding the formula terminator. The positive literal counter advances to position n and the unary fuel is restored. Runtime n*(2*c(n)+19)+6.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_head_positive_clause {k G : Nat} (hk : 7 ≤ k) (hG : 4 ≤ G) :
∃ R : Machine, TuringMachine k G R ∧
∀ (sh : Shape) (t j n a b : Nat) (input : Tape) (bits : List Bool)
(flag : Tape) (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 c := fun q => literalN (.Pos (sh.headVar t j q))
let chunk := true :: encodeListNat ((List.range n).map c)
Transforms R
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate b true)), 1 + b) ::
(contents (boolsToSymbols (List.replicate (c 0) true)), 1 + c 0) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: flag :: (fuel, 1) :: saved)
(n * (2 * c n + 19) + 6)
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate b true)), 1 + b) ::
(contents (boolsToSymbols (List.replicate (c n) true)), 1 + c n) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) :: flag :: (fuel, 1) :: saved) := by sorrySource
Runtime-sized distinct-position filtering for the Cook–Levin head constraints.