Cook–Levin machines: transition clauses on every position of one tape
ProvedCookLevin.machine_emit_transition_tape_positionscomplexitycook-levinloopsturing-machines
Emit both guarded transition clauses at each position from zero through n, in order. A first body handles the truncated left-movement boundary; a reusable unary loop handles positive positions. State/read bases and fuel are preserved, position counters finish at n+1, and the 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_emit_transition_tape_positions {k G : Nat} (hk : 8 ≤ k) (hG : 4 ≤ G)
(tapes symbols q : Nat) (rs : List Symbol) (action : Action) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t j n : Nat) (input : Tape) (bits : List Bool)
(fuel : Nat → Symbol) (saved : List Tape),
sh.k = tapes → sh.G = symbols → saved.length + 8 = k →
fuel 0 ≠ oneSymbol →
(∀ i, i < n → fuel (1 + i) = oneSymbol) →
fuel (1 + n) ≠ oneSymbol →
let a := literalN (.Neg (sh.stateVar t 0))
let b := literalN (.Neg (sh.readVar t 0 0))
let c := fun p => literalN (.Neg (sh.headVar t j p))
let d := fun p => literalN (.Pos (sh.headVar (t + 1) j (movePos action.2 p)))
let e := fun p => literalN (.Pos (sh.cellVar (t + 1) j p blankSymbol))
let chunk := (List.range (n + 1)).flatMap fun p =>
(encodeFormula
[guardClause sh t q rs ++ [Literal.Neg (sh.headVar t j p),
Literal.Pos (sh.headVar (t + 1) j (movePos action.2 p))],
guardClause sh t q rs ++ [Literal.Neg (sh.headVar t j p),
Literal.Pos (sh.cellVar (t + 1) j p action.1)]]).dropLast
Transforms R
(input ::
(contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate b true)), 1 + b) ::
(contents (boolsToSymbols (List.replicate (c 0) true)), 1 + c 0) ::
(contents (boolsToSymbols (List.replicate (d 0) true)), 1 + d 0) ::
(contents (boolsToSymbols (List.replicate (e 0) true)), 1 + e 0) ::
(contents (boolsToSymbols bits), 1 + bits.length) ::
(fuel, 1) :: saved)
((n + 1) * (A * (a + b + c (n + 1) + d (n + 1) + e (n + 1)) + B) + 4)
(input ::
(contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate b true)), 1 + b) ::
(contents (boolsToSymbols (List.replicate (c (n + 1)) true)), 1 + c (n + 1)) ::
(contents (boolsToSymbols (List.replicate (d (n + 1)) true)), 1 + d (n + 1)) ::
(contents (boolsToSymbols (List.replicate (e (n + 1)) true)), 1 + e (n + 1)) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
(fuel, 1) :: saved) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.