Cook–Levin machines: complete link emitter from a work bank
ProvedCookLevin.machine_link_clause_emitter_from_bankcomplexitycook-levinloopsturing-machines
Emit the complete actual linkClauses formula from two computed unary fuel tapes after an arbitrary saved work bank, followed by three blank counter tapes and a blank output. All six work heads begin zero. The machine initializes literal counters to 2, 0, 7, emits every link clause with the stated bound and canonical output, and preserves the preceding input and work bank. Position fuel marker and prefix/termination assumptions are explicit.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_link_clause_emitter_from_bank {a G : Nat} (hG : 4 ≤ G)
(tapes symbols : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine (a + 7) G R ∧
∀ (sh : Shape) (input : Tape) (times positions : Nat → Symbol) (saved : List Tape),
sh.k = tapes → sh.G = symbols → saved.length = a →
positions 0 ≠ oneSymbol →
(∀ i, i < sh.T + 1 → positions (1 + i) = oneSymbol) →
positions (1 + (sh.T + 1)) ≠ oneSymbol →
(∀ i, i < sh.T + 1 → times (1 + i) = oneSymbol) →
times (1 + (sh.T + 1)) ≠ oneSymbol →
let n := sh.T + 1
let v := 8 * sh.P * tapes * n + 2
let w := 8 * symbols * sh.P * tapes * n
let z := 8 * symbols * tapes * n + 7
let output := encodeFormula (linkClauses sh)
Transforms R
(input :: (saved ++ [(times, 0), (positions, 0), (contents [], 0), (contents [], 0),
(contents [], 0), (contents [], 0)]))
(n * (tapes * (n * (A * (v + w + z) + B + 6) + 4 + (8 + 16 * symbols)) + 3) + 17)
(input :: (saved ++ [(times, 1 + n), (positions, 1),
(contents (boolsToSymbols (List.replicate v true)), 1 + v),
(contents (boolsToSymbols (List.replicate w true)), 1 + w),
(contents (boolsToSymbols (List.replicate z true)), 1 + z),
(contents (boolsToSymbols output), 1 + output.length)])) := by sorrySource
Compose accepted literal emission, fixed counter increments, and reusable unary iteration with an exact output-prefix invariant.