Cook–Levin machines: transition commands block
ProvedCookLevin.machine_transition_clause_emitter_from_counterscomplexitycook-levinloopsturing-machines
Emit exactly the entire transitionClauses formula, including its terminator, from prepared counters and two unary width fuels. The inner fuel is restored while the outer fuel iterates time; runtime is explicitly bounded.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_transition_clause_emitter_from_counters {k G : Nat} (hk : 9 ≤ k)
(hG : 4 ≤ G) (M : Machine) (tapes symbols : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (input : Tape) (positions times : Nat → Symbol) (saved : List Tape),
sh.k = tapes → sh.G = symbols → sh.Q = M.length → saved.length + 9 = k →
positions 0 ≠ oneSymbol →
(∀ i, i < sh.T → positions (1 + i) = oneSymbol) →
positions (1 + sh.T) ≠ oneSymbol →
(∀ i, i < sh.T → times (1 + i) = oneSymbol) →
times (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 j => literalN (.Neg (sh.headVar t j 0))
let d := fun t j => literalN (.Pos (sh.headVar (t + 1) j 0))
let e := fun t j => literalN (.Pos (sh.cellVar (t + 1) j 0 blankSymbol))
let n := sh.T
let output := encodeFormula (transitionClauses sh M)
Transforms R
(input ::
(contents (boolsToSymbols (List.replicate (a 0) true)), 1 + a 0) ::
(contents (boolsToSymbols (List.replicate (b 0) true)), 1 + b 0) ::
(contents (boolsToSymbols (List.replicate (c 0 0) true)), 1 + c 0 0) ::
(contents (boolsToSymbols (List.replicate (d 0 0) true)), 1 + d 0 0) ::
(contents (boolsToSymbols (List.replicate (e 0 0) true)), 1 + e 0 0) ::
(contents [], 1) :: (positions, 1) :: (times, 1) :: saved)
(n * ((n + 1) * (A * (a n + b n + c n tapes + d n tapes + e n tapes) + B) + 3) + 2)
(input ::
(contents (boolsToSymbols (List.replicate (a n) true)), 1 + a n) ::
(contents (boolsToSymbols (List.replicate (b n) true)), 1 + b n) ::
(contents (boolsToSymbols (List.replicate (c n 0) true)), 1 + c n 0) ::
(contents (boolsToSymbols (List.replicate (d n 0) true)), 1 + d n 0) ::
(contents (boolsToSymbols (List.replicate (e n 0) true)), 1 + e n 0) ::
(contents (boolsToSymbols output), 1 + output.length) :: (positions, 1) :: (times, 1 + n) :: saved) := by sorrySource
Transition-clause emission for the Cook–Levin reduction.