Cook–Levin machines: transition commands block
ProvedCookLevin.machine_advance_transition_timecomplexitycook-levinloopsturing-machines
Advance all five transition literal counters from time t to time t+1, preserving input, output and width fuel with a 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_advance_transition_time {k G : Nat} (hk : 8 ≤ k) (hG : 4 ≤ G)
(tapes symbols states : Nat) :
∃ R : Machine, ∃ D : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t : Nat) (input out : Tape)
(fuel : Nat → Symbol) (saved : List Tape),
sh.k = tapes → sh.G = symbols → sh.Q = states →
fuel 0 ≠ oneSymbol →
(∀ i, i < sh.T → fuel (1 + i) = oneSymbol) →
fuel (1 + sh.T) ≠ oneSymbol →
let a := fun t => literalN (.Neg (sh.stateVar t 0))
let b := fun t => literalN (.Neg (sh.readVar t 0 0))
let c := fun t => literalN (.Neg (sh.headVar t 0 0))
let d := fun t => literalN (.Pos (sh.headVar (t + 1) 0 0))
let e := fun t => literalN (.Pos (sh.cellVar (t + 1) 0 0 blankSymbol))
Transforms R
(input ::
(contents (boolsToSymbols (List.replicate (a t) true)), 1 + a t) ::
(contents (boolsToSymbols (List.replicate (b t) true)), 1 + b t) ::
(contents (boolsToSymbols (List.replicate (c t) true)), 1 + c t) ::
(contents (boolsToSymbols (List.replicate (d t) true)), 1 + d t) ::
(contents (boolsToSymbols (List.replicate (e t) true)), 1 + e t) :: out :: (fuel, 1) :: saved)
((sh.T + 1) * D)
(input ::
(contents (boolsToSymbols (List.replicate (a (t + 1)) true)), 1 + a (t + 1)) ::
(contents (boolsToSymbols (List.replicate (b (t + 1)) true)), 1 + b (t + 1)) ::
(contents (boolsToSymbols (List.replicate (c (t + 1)) true)), 1 + c (t + 1)) ::
(contents (boolsToSymbols (List.replicate (d (t + 1)) true)), 1 + d (t + 1)) ::
(contents (boolsToSymbols (List.replicate (e (t + 1)) true)), 1 + e (t + 1)) :: out :: (fuel, 1) :: saved) := by sorrySource
Transition-clause emission for the Cook–Levin reduction.