Cook–Levin machines: fixed unary subtraction
ProvedCookLevin.machine_subtract_fixed_unarycomplexitycook-levinloopsturing-machines
Subtract a fixed D from a canonical unary counter of length n+D, producing length n and its canonical end head. All other tapes and heads are preserved. Runtime is bounded by 2*D.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_subtract_fixed_unary {k G j : Nat} (hk : 2 ≤ k)
(hG : 4 ≤ G) (hj : 0 < j) (D : Nat) :
∃ R : Machine, TuringMachine k G R ∧
∀ (n : Nat) (left right : List Tape), left.length = j →
Transforms R
(left ++ (contents (boolsToSymbols (List.replicate (n + D) true)), 1 + (n + D)) :: right)
(2 * D)
(left ++ (contents (boolsToSymbols (List.replicate n true)), 1 + n) :: right) := by sorrySource
Runtime-sized distinct-position filtering for the Cook–Levin head constraints.