Cook–Levin machines: link clauses for a complete logical tape
ProvedCookLevin.machine_emit_link_tape_blockcomplexitycook-levinloopsturing-machines
Emit all link clauses for T+1 positions of one logical tape. Three unary literal counters advance to position zero of the next tape; the position fuel returns to head one. The extra head and cell strides account for the unused radix position. Exact stated runtime includes 8+16*symbols counter updates.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_link_tape_block {k G : Nat} (hk : 6 ≤ k)
(hG : 4 ≤ G) (symbols : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t j : Nat) (input : Tape) (bits : List Bool)
(fuel : Nat → Symbol) (saved : List Tape),
sh.G = symbols → saved.length + 6 = k →
fuel 0 ≠ oneSymbol →
(∀ i, i < sh.T + 1 → fuel (1 + i) = oneSymbol) →
fuel (1 + (sh.T + 1)) ≠ oneSymbol →
let a := fun j => literalN (.Neg (sh.headVar t j 0))
let b := fun j => literalN (.Neg (sh.cellVar t j 0 blankSymbol))
let c := fun j => literalN (.Pos (sh.readVar t j blankSymbol))
let chunk := (List.range (sh.T + 1)).flatMap fun p =>
(encodeFormula ((List.range sh.G).map fun s =>
[Literal.Neg (sh.headVar t j p), Literal.Neg (sh.cellVar t j p s),
Literal.Pos (sh.readVar t j s)])).dropLast
Transforms R
(input :: (contents (boolsToSymbols (List.replicate (a j) true)), 1 + a j) ::
(contents (boolsToSymbols (List.replicate (b j) true)), 1 + b j) ::
(contents (boolsToSymbols (List.replicate (c j) true)), 1 + c j) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: (fuel, 1) :: saved)
((sh.T + 1) * (A * (a (j + 1) + b (j + 1) + c (j + 1)) + B + 6) +
4 + (8 + 16 * symbols))
(input :: (contents (boolsToSymbols (List.replicate (a (j + 1)) true)), 1 + a (j + 1)) ::
(contents (boolsToSymbols (List.replicate (b (j + 1)) true)), 1 + b (j + 1)) ::
(contents (boolsToSymbols (List.replicate (c (j + 1)) true)), 1 + c (j + 1)) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
(fuel, 1) :: saved) := by sorrySource
Compose accepted literal emission, fixed counter increments, and reusable unary iteration with an exact output-prefix invariant.