Cook–Levin machines: uniform read-symbol clause body
ProvedCookLevin.machine_emit_read_clause_bodycomplexitycook-levinloopsturing-machines
For fixed tableau tape and symbol bounds, one well-formed Turing machine emits every exactly-one-read-symbol clause at a single time t. Its unary counter holds a=8symbolstapest and advances by 8symbolstapes. The actual formula block encoding is appended without its final terminator. Runtime is Aa+B for constants independent of time and width. Input and spectators are preserved. Zero tapes and zero symbols are included.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_read_clause_body {k G : Nat} (hk : 3 ≤ k) (hG : 4 ≤ G)
(tapes symbols : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t : Nat) (input : Tape) (bits : List Bool) (saved : List Tape),
(sh.k = tapes ∧ sh.G = symbols) → saved.length + 3 = k →
let a := 8 * symbols * tapes * t
let chunk := (encodeFormula ((List.range sh.k).flatMap fun j =>
exactlyOneOf (List.range sh.G) (sh.readVar t j))).dropLast
Transforms R
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: saved)
(A * a + B)
(input ::
(contents (boolsToSymbols (List.replicate (a + 8 * symbols * tapes) true)),
1 + (a + 8 * symbols * tapes)) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
saved) := by sorrySource
Compile a finite formula of unary literal offsets, identify it with the per-tape exactly-one-read-symbol constraints using injectivity in the symbol index, and compose the fixed common-offset increment.