Cook–Levin machines: emit the complete head formula from prepared counters
ProvedCookLevin.machine_head_clause_emitter_from_counterscomplexitycook-levinloopsturing-machines
Emit exactly encodeFormula(headClauses sh) from prepared literal counters and three unary fuels. Both position fuels are restored, the flag and input are preserved, and time fuel advances to its terminator. The runtime is n*(tapesn^2(A*(2*a+c)+B)+3)+2 for n=T+1 and final literal counters a,c.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_head_clause_emitter_from_counters {k G : Nat} (hk : 9 ≤ k)
(hG : 4 ≤ G) (tapes : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (input : Tape) (flag inner outer times : Nat → Symbol) (saved : List Tape),
sh.k = tapes → saved.length + 9 = 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 →
(∀ i, i < sh.T + 1 → times (1 + i) = oneSymbol) →
times (1 + (sh.T + 1)) ≠ oneSymbol →
let n := sh.T + 1
let a := 8 * sh.P * tapes * n + 2
let c := 8 * sh.P * tapes * n + 3
let output := encodeFormula (headClauses sh)
Transforms R
(input :: (contents (boolsToSymbols (List.replicate 2 true)), 3) ::
(contents (boolsToSymbols (List.replicate 2 true)), 3) :: (contents (boolsToSymbols (List.replicate 3 true)), 4) ::
(contents [], 1) ::
(flag, 1) :: (inner, 1) :: (outer, 1) :: (times, 1) :: saved)
(n * (tapes * (n^2 * (A * (a + a + c) + B)) + 3) + 2)
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
(contents (boolsToSymbols output), 1 + output.length) ::
(flag, 1) :: (inner, 1) :: (outer, 1) :: (times, 1 + n) :: saved) := by sorrySource
Runtime-sized distinct-position filtering for the Cook–Levin head constraints.