Cook–Levin machines: compare unary counters with head restoration
ProvedCookLevin.machine_compare_unary_counterscomplexitycook-levinloopsturing-machines
Compare two canonical unary counters, preserve their contents and restore both heads, writing only the equality flag on tape five. The input, spare, output and saved tapes are preserved. Runtime is at most 2*min(a,b)+4, including zero counters.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_compare_unary_counters {k G : Nat} (hk : 6 ≤ k) (hG : 4 ≤ G) :
∃ R : Machine, TuringMachine k G R ∧
∀ (a b : Nat) (input spare out : Tape) (flag : Nat → Symbol) (saved : List Tape),
Transforms R
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate b true)), 1 + b) ::
spare :: out :: (flag, 1) :: saved)
(2 * min a b + 4)
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate b true)), 1 + b) :: spare :: out ::
((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.