Cook–Levin machines: all state clauses from a unary time counter
ProvedCookLevin.machine_state_clause_emitter_from_countercomplexitycook-levinloopsturing-machines
For each fixed state bound Q, one well-formed Turing machine emits the complete encoding of all state clauses of every tableau with that state bound. It starts with a zero literal-offset counter, empty output, and a fuel tape whose one-symbol prefix has length T+1. The fuel contents outside that prefix are arbitrary, with a non-one terminator. Its runtime is n*(Aa+B+3)+2 where n=T+1 and a=8(Q+1)*n. The input and spectators are preserved, fuel contents are unchanged, and the final counter and formula output are canonical.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_state_clause_emitter_from_counter {k G : Nat} (hk : 4 ≤ k)
(hG : 4 ≤ G) (Q : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (input : Tape) (fuel : Nat → Symbol) (saved : List Tape),
sh.Q = Q → saved.length + 4 = k →
(∀ i, i < sh.T + 1 → fuel (1 + i) = oneSymbol) →
fuel (1 + (sh.T + 1)) ≠ oneSymbol →
let n := sh.T + 1
let a := 8 * (Q + 1) * n
let output := encodeFormula (stateClauses sh)
Transforms R
(input :: (contents [], 1) :: (contents [], 1) :: (fuel, 1) :: saved)
(n * (A * a + B + 3) + 2)
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols output), 1 + output.length) ::
(fuel, 1 + n) :: saved) := by sorrySource
Repeat the accepted exactly-one-state block emitter using the accepted unary-fuel loop, with a uniform affine bound at the final literal counter. Append the outer formula terminator and identify the concatenated blocks with the actual stateClauses definition.