Cook–Levin machines: transition commands block
ProvedCookLevin.machine_advance_transition_position_counterscomplexitycook-levinloopsturing-machines
Advance three unary position counters by fixed multiples of the width plus two, preserving the reusable width fuel and every other tape with an explicit linear runtime.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_advance_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 true)), 1 + c) ::
(contents (boolsToSymbols (List.replicate d true)), 1 + d) ::
(contents (boolsToSymbols (List.replicate e true)), 1 + e) :: out :: (fuel, 1) :: saved)
(n * (2 * H + C + 6) + 4 * H + 2 * C + 4)
(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) := by sorrySource
Transition-clause emission for the Cook–Levin reduction.