Cook–Levin machines: fuel bank
ProvedCookLevin.machine_inertia_clause_emitter_from_fuel_bankcomplexitycook-levinloopsturing-machines
Emit the complete inertia formula from two unary fuel tapes of lengths T and T+1, with three blank counters and blank output, all heads initially zero. Construct the next-time-cell counter directly from the position fuel, preserve the protected work bank, and give the full runtime including initialization. Zero logical tapes, symbols, and time are included.
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_fuel_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 [], 0),
(contents [], 0)]))
(n * (tapes * ((sh.T + 1) * (A * (v + w + z) + B + 6) + 4 + (8 + 16 * symbols)) + 3) + (sh.T + 1) * (8 * symbols * tapes + 6) + 8 * symbols * tapes + 16)
(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.