Cook–Levin machines: complete inertia formula from counters
ProvedCookLevin.machine_inertia_clause_emitter_from_counterscomplexitycook-levinloopsturing-machines
Emit the complete actual inertia formula from prepared unary literal counters and two unary fuel tapes. The time fuel has length T, while the reusable position fuel has length T+1. The initial next-time-cell counter includes the full position radix and logical tape count. The output includes the final formula terminator and has an explicit runtime bound.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_inertia_clause_emitter_from_counters {k G : Nat} (hk : 7 ≤ 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 + 7 = k →
positions 0 ≠ oneSymbol →
(∀ i, i < sh.T + 1 → positions (1 + i) = oneSymbol) →
positions (1 + (sh.T + 1)) ≠ oneSymbol →
(∀ i, i < sh.T → times (1 + i) = oneSymbol) →
times (1 + sh.T) ≠ oneSymbol →
let n := sh.T
let a := 8 * sh.P * tapes * n + 3
let b := 8 * symbols * sh.P * tapes * n
let c := 8 * symbols * sh.P * tapes * (n + 1) + 1
let output := encodeFormula (inertiaClauses sh)
Transforms R
(input :: (contents (boolsToSymbols (List.replicate 3 true)), 4) ::
(contents [], 1) :: (contents (boolsToSymbols (List.replicate (8 * symbols * sh.P * tapes + 1) true)),
1 + (8 * symbols * sh.P * tapes + 1)) ::
(contents [], 1) ::
(positions, 1) :: (times, 1) :: saved)
(n * (tapes * ((sh.T + 1) * (A * (a + b + c) + B + 6) + 4 + (8 + 16 * symbols)) + 3) + 2)
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate b true)), 1 + b) ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
(contents (boolsToSymbols output), 1 + output.length) ::
(positions, 1) :: (times, 1 + n) :: saved) := by sorrySource
Compose the three-counter template compiler, fixed counter strides and reusable unary iteration with the actual inertia-clause encoding.