Cook–Levin machines: read-symbol clauses from a computed time-count bank
ProvedCookLevin.machine_read_clause_emitter_from_bankcomplexitycook-levinloopsturing-machines
For fixed tableau tape and symbol bounds, one well-formed Turing machine emits the complete read-symbol clause formula from the physical layout input, saved work bank, unary time count, and two blank tapes. All work heads initially sit at zero. For n=T+1 and v=8symbolstapesn, runtime is n(A*v+B+3)+5. The final tape contains the canonical formula encoding. Input, saved bank, and fuel contents are preserved; the saved bank and tableau bounds may be zero.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_read_clause_emitter_from_bank {a G : Nat} (hG : 4 ≤ G) (tapes symbols : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine (a + 4) G R ∧
∀ (sh : Shape) (input : Tape) (fuel : Nat → Symbol) (saved : List Tape),
(sh.k = tapes ∧ sh.G = symbols) → 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 * symbols * tapes * n
let output := encodeFormula (readClauses 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
Repeat the accepted per-time read-symbol emitter for all T+1 time points, append the formula terminator, initialize work heads, and permute the logical tapes into the physical computed-width bank layout.