Cook–Levin machines: polynomial-time halt clauses from unary width
ProvedCookLevin.haltClauseEmitter_of_unary_widthcomplexitycook-levinloopsturing-machines
Any polynomial-time unary width function suffices to compute the full encoded haltClauses 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 head and cell counters from the position fuel, initializes the other counters, emits every time/tape/position/symbol halt 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.haltClauseEmitter_of_unary_width (k G Q : Nat) (w : List Bool → Nat)
(hw : IsPolyTimeComputable (fun x => List.replicate (w x) true)) :
IsPolyTimeComputable (fun x => encodeFormula (haltClauses ⟨k, G, Q, w x⟩)) := by sorrySource
Compose accepted literal emission, fixed counter increments, and reusable unary iteration with an exact output-prefix invariant.