Cook–Levin machines: transition position body and counter advances
ProvedCookLevin.machine_emit_transition_position_bodycomplexitycook-levinloopsturing-machines
Append the exact head-movement and written-symbol clauses and advance their three position counters. State and read bases remain unchanged. A parameterized next-head stride supports both the left-movement boundary at zero and uniform positive-position iteration.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_transition_position_body {k G : Nat} (hk : 7 ≤ k) (hG : 4 ≤ G)
(tapes symbols q advance : Nat) (rs : List Symbol) (action : Action) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t j p : Nat) (input : Tape) (bits : List Bool) (saved : List Tape),
sh.k = tapes → sh.G = symbols → saved.length + 7 = k →
let a := literalN (.Neg (sh.stateVar t 0))
let b := literalN (.Neg (sh.readVar t 0 0))
let c := literalN (.Neg (sh.headVar t j p))
let d := literalN (.Pos (sh.headVar (t + 1) j (movePos action.2 p)))
let e := literalN (.Pos (sh.cellVar (t + 1) j p blankSymbol))
let chunk := (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 true)), 1 + c) ::
(contents (boolsToSymbols (List.replicate d true)), 1 + d) ::
(contents (boolsToSymbols (List.replicate e true)), 1 + e) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: saved) (A * (a + b + c + d + e) + B)
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate b true)), 1 + b) ::
(contents (boolsToSymbols (List.replicate (c + 8) true)), 1 + (c + 8)) ::
(contents (boolsToSymbols (List.replicate (d + 8 * advance) true)), 1 + (d + 8 * advance)) ::
(contents (boolsToSymbols (List.replicate (e + 8 * symbols) true)), 1 + (e + 8 * symbols)) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) :: saved) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.