Cook–Levin machines: emit a complete head tape block
ProvedCookLevin.machine_emit_head_tape_blockcomplexitycook-levinloopsturing-machines
Emit exactly the encoded exactly-one head-position formula for one time and logical tape, advance all three literal counters to the next logical tape, and restore both position fuels. Preserve a flag initially containing oneSymbol at cell one. Runtime at most (T+1)^2 times an affine function of the final literal counters.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_head_tape_block {k G : Nat} (hk : 8 ≤ k) (hG : 4 ≤ G) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t j : Nat) (input : Tape) (bits : List Bool)
(flag inner outer : Nat → Symbol) (saved : List Tape),
saved.length + 8 = k → flag 1 = oneSymbol →
inner 0 ≠ oneSymbol → outer 0 ≠ oneSymbol →
(∀ i, i < sh.T + 1 → inner (1 + i) = oneSymbol) →
(∀ i, i < sh.T + 1 → outer (1 + i) = oneSymbol) →
inner (1 + (sh.T + 1)) ≠ oneSymbol → outer (1 + (sh.T + 1)) ≠ oneSymbol →
let a := fun j => literalN (.Neg (sh.headVar t j 0))
let c := fun j => literalN (.Pos (sh.headVar t j 0))
let chunk := (encodeFormula (exactlyOneOf (List.range (sh.T + 1)) (sh.headVar t j))).dropLast
Transforms R
(input :: (contents (boolsToSymbols (List.replicate (a j) true)), 1 + a j) ::
(contents (boolsToSymbols (List.replicate (a j) true)), 1 + a j) ::
(contents (boolsToSymbols (List.replicate (c j) true)), 1 + c j) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: (flag, 1) :: (inner, 1) :: (outer, 1) :: saved)
((sh.T + 1)^2 * (A * (a (j + 1) + a (j + 1) + c (j + 1)) + B))
(input :: (contents (boolsToSymbols (List.replicate (a (j + 1)) true)), 1 + a (j + 1)) ::
(contents (boolsToSymbols (List.replicate (a (j + 1)) true)), 1 + a (j + 1)) ::
(contents (boolsToSymbols (List.replicate (c (j + 1)) true)), 1 + c (j + 1)) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
(flag, 1) ::
(inner, 1) :: (outer, 1) :: saved) := by sorrySource
Runtime-sized distinct-position filtering for the Cook–Levin head constraints.