Cook–Levin machines: certificate-cell formula from computed bound tapes
ProvedCookLevin.machine_certificate_cells_from_bankcomplexitycook-levinloopsturing-machines
Emit the complete certificate-cell initialization formula from independent unary width and canonical certificate-bound tapes. Initialize the width-dependent literal counter, preserve the saved work bank, and write canonical output. The explicit runtime includes initialization, counter construction, scanning and final encoding markers.
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_bank {a G : Nat} (hG : 4 ≤ G) (alphabet : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine (a + 5) G R ∧
∀ (sh : Shape) (m : Nat) (input : Tape) (fuel : Nat → Symbol) (saved : List Tape),
sh.G = alphabet → saved.length = a → 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 :: (saved ++ [(fuel, 0), (contents (List.replicate m oneSymbol), 0),
(contents [], 0), (contents [], 0)]))
(n * (A * v + B + 8 * alphabet + 9) + 8 * alphabet + 10)
(input :: (saved ++ [(fuel, 1 + n), (contents (List.replicate m oneSymbol), n),
(contents (boolsToSymbols (List.replicate v true)), 1 + v),
(contents (boolsToSymbols output), 1 + output.length)])) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.