Cook–Levin machines: polynomial-time inertia clauses from unary width
ProvedCookLevin.inertiaClauseEmitter_of_unary_widthcomplexitycook-levinloopsturing-machines
Any polynomial-time unary width function suffices to compute the full encoded inertiaClauses formula using the actual tableau numbering. The standard-input Turing machine computes width plus one, copies reusable position fuel, shortens the time fuel by one, constructs the next-time-cell counter from the position fuel, initializes the other counters, emits every time/tape/position/symbol inertia clause, and produces canonical output. The proof gives a polynomial of degree four times the unary source exponent. All natural tape, alphabet and state bounds, including zero, are allowed.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.inertiaClauseEmitter_of_unary_width (k G Q : Nat) (w : List Bool → Nat)
(hw : IsPolyTimeComputable (fun x => List.replicate (w x) true)) :
IsPolyTimeComputable (fun x => encodeFormula (inertiaClauses ⟨k, G, Q, w x⟩)) := by sorrySource
Compose accepted literal emission, fixed counter increments, and reusable unary iteration with an exact output-prefix invariant.