Cook–Levin machines: guarded transition head and write clauses
ProvedCookLevin.machine_emit_transition_position_literal_blockcomplexitycook-levinloopsturing-machines
Compile both guarded transition clauses at one position from five runtime unary counters. The fixed scanned-symbol tuple supplies the guard offsets, and the fixed action supplies the written symbol and head direction. Counters are preserved and the exact formula encoding is appended without its final terminator.
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_literal_block {k G : Nat} (hk : 7 ≤ 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 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 true)), 1 + c) ::
(contents (boolsToSymbols (List.replicate d true)), 1 + d) ::
(contents (boolsToSymbols (List.replicate e true)), 1 + e) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) :: saved) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.