Cook–Levin machines: complete cell tape block
ProvedCookLevin.machine_emit_cell_tape_blockcomplexitycook-levinloopsturing-machines
One fixed well-formed machine emits all exactly-one-symbol constraints for a logical tape at a specified time, over T+1 positions. It appends the actual encoded blocks, restores the unary position fuel, and advances the counter to position zero of the next tape, crossing the unused radix position. Its runtime is bounded by (T+1)(Aa(nextTape)+B+6)+4+8*symbols. Input and spectators are preserved; zero symbols are allowed.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_cell_tape_block {k G : Nat} (hk : 4 ≤ 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 + 4 = 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.cellVar t j 0 blankSymbol))
let chunk := (List.range (sh.T + 1)).flatMap fun p =>
(encodeFormula (exactlyOneOf (List.range sh.G) (sh.cellVar t j p))).dropLast
Transforms R
(input :: (contents (boolsToSymbols (List.replicate (a j) true)), 1 + a j) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: (fuel, 1) :: saved)
((sh.T + 1) * (A * a (j + 1) + B + 6) + 4 + 8 * symbols)
(input :: (contents (boolsToSymbols (List.replicate (a (j + 1)) true)), 1 + a (j + 1)) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
(fuel, 1) :: saved) := by sorrySource
Compose the accepted cell-position loop with a fixed unary counter increment and prove the radix-crossing identity. Bound all literal counters by the next tape offset.