Cook–Levin machines: blank-suffix emission from computation banks
ProvedCookLevin.machine_blank_suffix_emitter_from_bankscomplexitycook-levinloopsturing-machines
A fixed machine emits the complete blank-suffix formula from unary literal and width outputs held between two arbitrary computation work banks. Two fresh final tapes hold the canonical counter and the final formula. The input, both work banks, and computed source contents are preserved. Tape renaming adds no runtime overhead: the bound remains a_initial + width*(4a_final+16symbols+16)+7.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_blank_suffix_emitter_from_banks {a b G : Nat} (hG : 4 ≤ G) (symbols : Nat) :
∃ R : Machine, TuringMachine (a + b + 5) G R ∧
∀ (sh : Shape) (j : Nat) (input : Tape) (source fuel : Nat → Symbol)
(left right : List Tape),
sh.G = symbols → left.length = a → right.length = b →
let a₀ := literalN (.Neg (sh.cellVar 0 j 0 blankSymbol))
let aₙ := literalN (.Neg (sh.cellVar 0 j sh.T blankSymbol))
let output := encodeFormula (blankSuffixClauses sh j)
(∀ i, i < a₀ → source (1 + i) = oneSymbol) →
(¬ (source (1 + a₀) = zeroSymbol ∨ source (1 + a₀) = oneSymbol)) →
(∀ i, i < sh.T → fuel (1 + i) = oneSymbol) →
fuel (1 + sh.T) ≠ oneSymbol →
Transforms R
(input :: (left ++ (source, 0) :: (fuel, 0) ::
(right ++ [(contents [], 0), (contents [], 0)])))
(a₀ + sh.T * (4 * aₙ + 16 * symbols + 16) + 7)
(input :: (left ++ (source, 1 + a₀) :: (fuel, 1 + sh.T) ::
(right ++ [(contents (boolsToSymbols (List.replicate aₙ true)), 1 + aₙ),
(contents (boolsToSymbols output), 1 + output.length)]))) := by sorrySource
Relocate the computed-prefix clause emitter into two arbitrary computation work banks using an input-preserving tape permutation.