Cook–Levin machines: uniform exactly-one-state clause body
ProvedCookLevin.machine_emit_state_clause_bodycomplexitycook-levinloopsturing-machines
For every fixed state bound Q, one well-formed Turing machine emits all exactly-one-state clauses at any time t, for every tableau shape with that state bound. Its unary counter starts at the common literal offset 8*(Q+1)t and advances by 8(Q+1). The output appends the actual encoded formula block without its final terminator. Input and spectator tapes are unchanged. The runtime is A*a+B for constants A,B chosen with the machine independently of t and the tableau width. All state bounds, including Q=0, are covered.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_state_clause_body {k G : Nat} (hk : 3 ≤ k) (hG : 4 ≤ G)
(Q : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t : Nat) (input : Tape) (bits : List Bool) (saved : List Tape),
sh.Q = Q → saved.length + 3 = k →
let a := 8 * (Q + 1) * t
let chunk :=
(encodeFormula (exactlyOneOf (List.range sh.QQ) (sh.stateVar t))).dropLast
Transforms R
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: saved)
(A * a + B)
(input ::
(contents (boolsToSymbols (List.replicate (a + 8 * (Q + 1)) true)),
1 + (a + 8 * (Q + 1))) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
saved) := by sorrySource
Inductively compile finite lists of unary literal offsets, then identify the offset template with the actual exactlyOneOf state constraints using state-variable injectivity. Compose the block emitter with the fixed counter increment.