Cook–Levin machines: certificate initialization after independent computations
ProvedCookLevin.machine_certificate_cells_from_bankscomplexitycook-levinloopsturing-machines
Emit the exact certificate-cell formula with two saved work banks. The width and canonical certificate bound lie between those banks; the final two fresh tapes hold the initialized counter and canonical formula output. No runtime overhead from tape permutation.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_certificate_cells_from_banks {a b G : Nat} (hG : 4 ≤ G) (alphabet : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine (a + b + 5) G R ∧
∀ (sh : Shape) (m : Nat) (input : Tape) (fuel : Nat → Symbol) (left right : List Tape),
sh.G = alphabet → left.length = a → right.length = b → fuel 0 ≠ oneSymbol →
(∀ p, p < sh.T + 1 → fuel (1 + p) = oneSymbol) →
fuel (1 + (sh.T + 1)) ≠ oneSymbol →
let n := sh.T + 1
let v := 8 * alphabet * (2 * n + 1) + 1
let output := encodeFormula ((List.range n).map fun p =>
(reductionInit [] m 1 p).map fun s => Literal.Pos (sh.cellVar 0 1 p s))
Transforms R
(input :: (left ++ (fuel, 0) :: (contents (List.replicate m oneSymbol), 0) ::
(right ++ [(contents [], 0), (contents [], 0)])))
(n * (A * v + B + 8 * alphabet + 9) + 8 * alphabet + 10)
(input :: (left ++ (fuel, 1 + n) :: (contents (List.replicate m oneSymbol), n) ::
(right ++ [(contents (boolsToSymbols (List.replicate v true)), 1 + v),
(contents (boolsToSymbols output), 1 + output.length)]))) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.