Cook–Levin machines: transition counter restore
ProvedCookLevin.machine_restore_transition_position_counterscomplexitycook-levinloopsturing-machines
Restore three unary position counters by subtracting fixed multiples of the width plus two. Preserve the unary width fuel and give an explicit linear runtime bound.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_restore_transition_position_counters {k G : Nat} (hk : 8 ≤ k) (hG : 4 ≤ G)
(H C : Nat) :
∃ R : Machine, TuringMachine k G R ∧
∀ (c d e n : Nat) (input state readBase out : Tape) (fuel : Nat → Symbol) (saved : List Tape),
fuel 0 ≠ oneSymbol → (∀ i, i < n → fuel (1 + i) = oneSymbol) → fuel (1 + n) ≠ oneSymbol →
Transforms R
(input :: state :: readBase ::
(contents (boolsToSymbols (List.replicate (c + H * (n + 2)) true)), 1 + (c + H * (n + 2))) ::
(contents (boolsToSymbols (List.replicate (d + H * (n + 2)) true)), 1 + (d + H * (n + 2))) ::
(contents (boolsToSymbols (List.replicate (e + C * (n + 2)) true)), 1 + (e + C * (n + 2))) ::
out :: (fuel, 1) :: saved)
(n * (4 * H + 2 * C + 6) + 8 * H + 4 * C + 4)
(input :: state :: readBase ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
(contents (boolsToSymbols (List.replicate d true)), 1 + d) ::
(contents (boolsToSymbols (List.replicate e true)), 1 + e) :: out :: (fuel, 1) :: saved) := by sorrySource
Transition-clause emission for the Cook–Levin reduction.