Cook–Levin machines: reusable unary-fuel iteration
ProvedCookLevin.machine_repeat_unary_restore_preserves_turing_and_timecomplexitycook-levinloopsturing-machines
Every well-formed Turing machine body can be iterated under a unary fuel tape and then restore that fuel head to cell one for reuse by an outer loop. A trace of n body iterations, each bounded by T steps, takes at most n*(T+6)+4 steps. The body preserves fuel contents and head at each invocation; the loop preserves the complete fuel tape, including a non-one marker at zero and a non-one terminator. Other tapes follow the given body invariant. Zero iterations are included.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_repeat_unary_restore_preserves_turing_and_time {k G : Nat}
(j : Nat) (body : Machine) (hbody : TuringMachine k G body) :
∃ R : Machine, TuringMachine k G R ∧
∀ (n T : Nat) (fuel : Nat → Symbol) (left right : Nat → List Tape),
(∀ i, i ≤ n → (left i).length = j) →
fuel 0 ≠ oneSymbol →
(∀ i, i < n → fuel (1 + i) = oneSymbol) →
fuel (1 + n) ≠ oneSymbol →
(∀ i, i < n → Transforms body
(left i ++ (fuel, 1 + i) :: right i) T
(left (i + 1) ++ (fuel, 1 + i) :: right (i + 1))) →
Transforms R (left 0 ++ (fuel, 1) :: right 0) (n * (T + 6) + 4)
(left n ++ (fuel, 1) :: right n) := by sorrySource
Compose the accepted unary loop with a guarded leftward rewind and a final rightward head move. Verify the rewind against arbitrary prefix contents and preserve all tape data; combine the exact time bounds.