Cook–Levin machines: reset inner counter with reusable fuel
ProvedCookLevin.machine_subtract_unary_multiple_from_fuelcomplexitycook-levinloopsturing-machines
Reset a unary inner-loop counter from m+Dn to m by subtracting fixed stride D once per unary fuel mark. Restore the position fuel and preserve the outer, spare, output, flag and all saved tapes. Runtime n(2*D+6)+4.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_subtract_unary_multiple_from_fuel {k G : Nat}
(hk : 7 ≤ k) (hG : 4 ≤ G) (D : Nat) :
∃ R : Machine, TuringMachine k G R ∧
∀ (m n : Nat) (input ca cc out flag : Tape) (fuel : Nat → Symbol) (saved : List Tape),
fuel 0 ≠ oneSymbol →
(∀ i, i < n → fuel (1 + i) = oneSymbol) →
fuel (1 + n) ≠ oneSymbol →
Transforms R
(input :: ca :: (contents (boolsToSymbols (List.replicate (m + D * n) true)), 1 + (m + D * n)) ::
cc :: out :: flag :: (fuel, 1) :: saved)
(n * (2 * D + 6) + 4)
(input :: ca :: (contents (boolsToSymbols (List.replicate m true)), 1 + m) ::
cc :: out :: flag :: (fuel, 1) :: saved) := by sorrySource
Runtime-sized distinct-position filtering for the Cook–Levin head constraints.