Cook–Levin machines: reusable cell-position loop
ProvedCookLevin.machine_emit_cell_position_loopcomplexitycook-levinloopsturing-machines
A fixed machine emits every exactly-one-symbol clause for n consecutive positions of a specified tableau tape and time. It appends the actual encoded blocks to existing output and advances the unary literal counter. Runtime is n*(A*a(n)+B+6)+4. The unary fuel head returns to cell one, all fuel contents are preserved, and input and spectators are unchanged. This includes n=0 and zero symbols.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_cell_position_loop {k G : Nat} (hk : 4 ≤ k)
(hG : 4 ≤ G) (symbols : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t j n : Nat) (input : Tape) (bits : List Bool)
(fuel : Nat → Symbol) (saved : List Tape),
sh.G = symbols → saved.length + 4 = k →
fuel 0 ≠ oneSymbol →
(∀ i, i < n → fuel (1 + i) = oneSymbol) →
fuel (1 + n) ≠ oneSymbol →
let a := fun p => literalN (.Neg (sh.cellVar t j p blankSymbol))
let chunk := (List.range n).flatMap fun p =>
(encodeFormula (exactlyOneOf (List.range sh.G) (sh.cellVar t j p))).dropLast
Transforms R
(input :: (contents (boolsToSymbols (List.replicate (a 0) true)), 1 + a 0) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: (fuel, 1) :: saved)
(n * (A * a n + B + 6) + 4)
(input :: (contents (boolsToSymbols (List.replicate (a n) true)), 1 + a n) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
(fuel, 1) :: saved) := by sorrySource
Apply the accepted reusable unary loop to the cell-symbol clause body, with a monotone literal-counter bound and an invariant for the concatenated output prefix.