Cook–Levin machines: inertia emitter from a work bank
ProvedCookLevin.machine_inertia_clause_emitter_from_bankcomplexitycook-levinloopsturing-machines
Emit the complete inertia formula from a work bank containing two unary fuel tapes, blank head/current-cell counters, a computed canonical next-time-cell counter and blank output. All work heads start at zero. The bank prefix and input are preserved, the position fuel is restored, and an explicit runtime includes seeking the computed counter and all initialization. Zero logical tapes, symbols and time 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_inertia_clause_emitter_from_bank {a G : Nat} (hG : 4 ≤ G)
(tapes symbols : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine (a + 7) G R ∧
∀ (sh : Shape) (input : Tape) (times positions : Nat → Symbol) (saved : List Tape),
sh.k = tapes → sh.G = symbols → saved.length = a →
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 v := 8 * sh.P * tapes * n + 3
let w := 8 * symbols * sh.P * tapes * n
let z := 8 * symbols * sh.P * tapes * (n + 1) + 1
let output := encodeFormula (inertiaClauses sh)
Transforms R
(input :: (saved ++ [(times, 0), (positions, 0), (contents [], 0), (contents [], 0),
(contents (boolsToSymbols (List.replicate (8 * symbols * sh.P * tapes + 1) true)), 0),
(contents [], 0)]))
(3 * (8 * symbols * sh.P * tapes + 1) + n * (tapes * ((sh.T + 1) * (A * (v + w + z) + B + 6) + 4 + (8 + 16 * symbols)) + 3) + 12)
(input :: (saved ++ [(times, 1 + n), (positions, 1),
(contents (boolsToSymbols (List.replicate v true)), 1 + v),
(contents (boolsToSymbols (List.replicate w true)), 1 + w),
(contents (boolsToSymbols (List.replicate z true)), 1 + z),
(contents (boolsToSymbols output), 1 + output.length)])) := by sorrySource
Compose the three-counter template compiler, fixed counter strides and reusable unary iteration with the actual inertia-clause encoding.