Cook–Levin machines: complete link-clause emitter from unary counters
ProvedCookLevin.machine_link_clause_emitter_from_counterscomplexitycook-levinloopsturing-machines
Emit the complete actual linkClauses formula, including its final terminator, from two prepared unary fuel tapes and three canonical literal counters initially 2, 0, and 7. The position fuel is restored after every time slice; time fuel advances to the terminator. The explicit runtime bound covers all time slices, logical tapes, positions and symbols, including zero tape and alphabet bounds.
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_counters {k G : Nat} (hk : 7 ≤ k)
(hG : 4 ≤ G) (tapes symbols : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (input : Tape) (positions times : Nat → Symbol) (saved : List Tape),
sh.k = tapes → sh.G = symbols → saved.length + 7 = k →
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 a := 8 * sh.P * tapes * n + 2
let b := 8 * symbols * sh.P * tapes * n
let c := 8 * symbols * tapes * n + 7
let output := encodeFormula (linkClauses sh)
Transforms R
(input :: (contents (boolsToSymbols (List.replicate 2 true)), 3) ::
(contents [], 1) :: (contents (boolsToSymbols (List.replicate 7 true)), 8) ::
(contents [], 1) ::
(positions, 1) :: (times, 1) :: saved)
(n * (tapes * (n * (A * (a + b + c) + B + 6) + 4 + (8 + 16 * symbols)) + 3) + 2)
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate b true)), 1 + b) ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
(contents (boolsToSymbols output), 1 + output.length) ::
(positions, 1) :: (times, 1 + n) :: saved) := by sorrySource
Compose accepted literal emission, fixed counter increments, and reusable unary iteration with an exact output-prefix invariant.