Cook–Levin machines: advance counter with reusable fuel
ProvedCookLevin.machine_add_unary_multiple_from_fuelcomplexitycook-levinloopsturing-machines
Advance a canonical unary counter from m to m+Dn by appending fixed stride D once per unary fuel mark. Restore the fuel and preserve every other tape. Runtime n(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_add_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 true)), 1 + m) ::
cc :: out :: flag :: (fuel, 1) :: saved)
(n * (D + 6) + 4)
(input :: ca :: (contents (boolsToSymbols (List.replicate (m + D * n) true)), 1 + (m + D * n)) ::
cc :: out :: flag :: (fuel, 1) :: saved) := by sorrySource
Runtime-sized distinct-position filtering for the Cook–Levin head constraints.