Cook–Levin: transition emitter with preserved saved tapes
ProvedCookLevin.machine_transition_clause_emitter_from_fuel_bankcomplexitycook-levinloopsturing-machines
Emit the complete transition formula from two unary width fuels and six blank tapes appended to an arbitrary preserved work bank. Tape permutation preserves the exact computation and runtime.
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_fuel_bank {v G : Nat} (hG : 4 ≤ G) (M : Machine) (tapes symbols : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine (v + 9) G R ∧
∀ (sh : Shape) (input : Tape) (times positions : Nat → Symbol) (saved : List Tape),
sh.k = tapes → sh.G = symbols → sh.Q = M.length → saved.length = v →
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 :: (saved ++ [(times, 0), (positions, 0), (contents [], 0),
(contents [], 0), (contents [], 0), (contents [], 0), (contents [], 0), (contents [], 0)]))
(n * ((n + 1) * (A * (a n + b n + c n tapes + d n tapes + e n tapes) + B) + 3) +
n * (8 * tapes + 8 * symbols * tapes + 6) + 16 * tapes + 16 * symbols * tapes + 30)
(input :: (saved ++ [(times, 1 + n), (positions, 1),
(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)])) := by sorrySource
Transition-clause emission for the Cook–Levin reduction.