Cook–Levin machines: state clauses from a computed time-count bank
ProvedCookLevin.machine_state_clause_emitter_from_bankcomplexitycook-levinloopsturing-machines
For fixed Q and alphabet G at least four, a well-formed machine emits all state clauses from the physical layout input, saved work bank, unary time-count tape, and two blank tapes. All work heads initially sit at zero. The program and constants A,B are independent of tableau width and tape data. With n=T+1 and v=8*(Q+1)n, runtime is n(A*v+B+3)+5. The final tape holds the canonical formula encoding, the preceding tape the canonical offset counter. Input, saved work tapes and fuel contents are preserved. The work bank can be empty; arbitrary data after the fuel terminator is allowed.
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_bank {a G : Nat} (hG : 4 ≤ G) (Q : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine (a + 4) G R ∧
∀ (sh : Shape) (input : Tape) (fuel : Nat → Symbol) (saved : List Tape),
sh.Q = Q → saved.length = a →
(∀ i, i < sh.T + 1 → fuel (1 + i) = oneSymbol) →
fuel (1 + (sh.T + 1)) ≠ oneSymbol →
let n := sh.T + 1
let v := 8 * (Q + 1) * n
let output := encodeFormula (stateClauses sh)
Transforms R
(input :: (saved ++ [(fuel, 0), (contents [], 0), (contents [], 0)]))
(n * (A * v + B + 3) + 5)
(input :: (saved ++ [(fuel, 1 + n),
(contents (boolsToSymbols (List.replicate v true)), 1 + v),
(contents (boolsToSymbols output), 1 + output.length)])) := by sorrySource
Initialize three heads using write-back commands, then permute the accepted state-clause loop into the computed-width bank layout. Prove the permutation fixes input tape zero and preserves every bounded execution without runtime overhead.