Cook–Levin machines: emit distinct runtime counter pairs
ProvedCookLevin.machine_emit_distinct_counter_paircomplexitycook-levinloopsturing-machines
Emit a two-literal clause from two runtime unary counters exactly when they differ. Preserve the counters and record equality on tape five. The output excludes the formula terminator; runtime is affine in the sum of the three counters.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_distinct_counter_pair {k G : Nat} (hk : 6 ≤ k) (hG : 4 ≤ G) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (a b c : Nat) (input : Tape) (bits : List Bool)
(flag : Nat → Symbol) (saved : List Tape),
saved.length + 6 = k →
let chunk := if a = b then [] else true :: encodeListNat [a, b]
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) :: (flag, 1) :: 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) ::
((fun i => if i = 1 then boolSym (decide (a = b)) else flag i), 1) :: saved) := by sorrySource
Runtime-sized distinct-position filtering for the Cook–Levin head constraints.