Cook–Levin machines: polynomial-time head clauses from unary width
ProvedCookLevin.headClauseEmitter_of_unary_widthcomplexitycook-levinloopsturing-machines
Any polynomial-time unary width function suffices to compute the full encoded headClauses formula using the actual tableau numbering. The standard-input Turing machine computes width plus one, makes two reusable position fuel copies, initializes all counters, emits every time/tape exactly-one head constraint, and produces canonical output. The proof gives a polynomial of degree five 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.headClauseEmitter_of_unary_width (k G Q : Nat) (w : List Bool → Nat)
(hw : IsPolyTimeComputable (fun x => List.replicate (w x) true)) :
IsPolyTimeComputable (fun x => encodeFormula (headClauses ⟨k, G, Q, w x⟩)) := by sorrySource
Compose accepted literal emission, fixed counter increments, and reusable unary iteration with an exact output-prefix invariant.