Cook–Levin machines: complete cell-constraint formula from unary counters
ProvedCookLevin.machine_cell_clause_emitter_from_counterscomplexitycook-levinloopsturing-machines
For fixed tape and symbol bounds, one well-formed machine emits the full actual cellClauses formula, including its final terminator, from prepared position and time unary fuel. With n=T+1 and a=8symbols(T+2)tapesn, runtime is n*(tapes*(n*(Aa+B+6)+4+8symbols)+3)+2. The position fuel is restored; the time fuel advances to its terminator. Input, fuel contents, and spectators are preserved. Zero tape and symbol bounds are allowed.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_cell_clause_emitter_from_counters {k G : Nat} (hk : 5 ≤ k)
(hG : 4 ≤ G) (tapes symbols : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (input : Tape) (positions times : Nat → Symbol) (saved : List Tape),
sh.k = tapes → sh.G = symbols → saved.length + 5 = k →
positions 0 ≠ oneSymbol →
(∀ i, i < sh.T + 1 → positions (1 + i) = oneSymbol) →
positions (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 * symbols * sh.P * tapes * n
let output := encodeFormula (cellClauses sh)
Transforms R
(input :: (contents [], 1) :: (contents [], 1) ::
(positions, 1) :: (times, 1) :: saved)
(n * (tapes * (n * (A * a + B + 6) + 4 + 8 * symbols) + 3) + 2)
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols output), 1 + output.length) ::
(positions, 1) :: (times, 1 + n) :: saved) := by sorrySource
Nest the accepted cell time block in a unary time loop, identify the accumulated blocks with the complete cellClauses encoding, and append the final formula terminator.