Cook–Levin machines: conditional execution with one control step
ProvedCookLevin.machine_conditional_preserves_turing_and_timecomplexitycook-levinloopsturing-machines
Run a well-formed machine body once when a read-only guard is true, otherwise preserve all tapes. The conditional uses no additional tapes and takes at most one step beyond the body time bound.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_conditional_preserves_turing_and_time {k G : Nat}
(guard : List Symbol → Bool) (body : Machine) (hbody : TuringMachine k G body) :
∃ R : Machine, TuringMachine k G R ∧
∀ (tps finalTps : List Tape) (T : Nat),
(guard (CookLevin.read tps) = true → Transforms body tps T finalTps) →
Transforms R tps (T + 1) (if guard (CookLevin.read tps) then finalTps else tps) := by sorrySource
Runtime-sized distinct-position filtering for the Cook–Levin head constraints.