Cook–Levin machines: exact certificate-cell initialization
ProvedCookLevin.machine_emit_certificate_cell_bodycomplexitycook-levinloopsturing-machines
Emit the exact positive clause for a certificate cell from reductionInit. A unary bound tape distinguishes the start marker, the three-symbol free region and the forced-blank suffix. Advance the bound head and cell counter; preserve the input and bound contents.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_certificate_cell_body {k G : Nat} (hk : 4 ≤ k) (hG : 4 ≤ G)
(alphabet : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (m p : Nat) (input : Tape)
(bits : List Bool) (saved : List Tape),
sh.G = alphabet → saved.length + 4 = k →
let a := literalN (.Pos (sh.cellVar 0 1 p 0))
let a' := literalN (.Pos (sh.cellVar 0 1 (p + 1) 0))
let chunk := true :: encodeListNat
(clauseN ((reductionInit [] m 1 p).map fun s => Literal.Pos (sh.cellVar 0 1 p s)))
Transforms R
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols bits), 1 + bits.length) ::
(contents (List.replicate m oneSymbol), p) :: saved)
(A * a + B)
(input :: (contents (boolsToSymbols (List.replicate a' true)), 1 + a') ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
(contents (List.replicate m oneSymbol), p + 1) :: saved) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.