Cook–Levin machines: blank-suffix emission from computed unary prefixes
ProvedCookLevin.machine_blank_suffix_emitter_from_computed_prefixescomplexitycook-levinloopsturing-machines
For each fixed symbol bound, one machine emits the entire blank-suffix formula from computed unary prefixes for its initial literal number and width. Both source tapes may have arbitrary data beyond their terminators. Two fresh tapes provide a canonical counter and the output. All work heads initially equal zero. Runtime is at most a_initial + width*(4a_final+16symbols+16)+7. Input, source contents, and all spectators are preserved; output is on tape four.
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_computed_prefixes {k G : Nat}
(hk : 5 ≤ k) (hG : 4 ≤ G) (symbols : Nat) :
∃ R : Machine, TuringMachine k G R ∧
∀ (sh : Shape) (j : Nat) (input : Tape) (source fuel : Nat → Symbol) (saved : List Tape),
sh.G = symbols → saved.length + 5 = k →
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 :: (source, 0) :: (contents [], 0) :: (fuel, 0) :: (contents [], 0) :: saved)
(a₀ + sh.T * (4 * aₙ + 16 * symbols + 16) + 7)
(input :: (source, 1 + a₀) ::
(contents (boolsToSymbols (List.replicate aₙ true)), 1 + aₙ) ::
(fuel, 1 + sh.T) ::
(contents (boolsToSymbols output), 1 + output.length) :: saved) := by sorrySource
Canonicalize the computed literal counter, permute the five-tape interface, advance output and width heads, and run the actual clause loop.