Cook–Levin machines: inertia tape block
ProvedCookLevin.machine_emit_inertia_tape_blockcomplexitycook-levinloopsturing-machines
Emit all actual inertia constraints on one logical tape and advance all three literal counters across the unused position radix entry to the next logical tape. The unary position fuel is restored; the runtime is explicitly bounded, including zero symbols.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_inertia_tape_block {k G : Nat} (hk : 6 ≤ k)
(hG : 4 ≤ G) (symbols : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t j : Nat) (input : Tape) (bits : List Bool)
(fuel : Nat → Symbol) (saved : List Tape),
sh.G = symbols → saved.length + 6 = k →
fuel 0 ≠ oneSymbol →
(∀ i, i < sh.T + 1 → fuel (1 + i) = oneSymbol) →
fuel (1 + (sh.T + 1)) ≠ oneSymbol →
let a := fun j => literalN (.Pos (sh.headVar t j 0))
let b := fun j => literalN (.Neg (sh.cellVar t j 0 blankSymbol))
let c := fun j => literalN (.Pos (sh.cellVar (t + 1) j 0 blankSymbol))
let chunk := (List.range (sh.T + 1)).flatMap fun p =>
(encodeFormula ((List.range sh.G).map fun s =>
[Literal.Pos (sh.headVar t j p), Literal.Neg (sh.cellVar t j p s),
Literal.Pos (sh.cellVar (t + 1) j p s)])).dropLast
Transforms R
(input :: (contents (boolsToSymbols (List.replicate (a j) true)), 1 + a j) ::
(contents (boolsToSymbols (List.replicate (b j) true)), 1 + b j) ::
(contents (boolsToSymbols (List.replicate (c j) true)), 1 + c j) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: (fuel, 1) :: saved)
((sh.T + 1) * (A * (a (j + 1) + b (j + 1) + c (j + 1)) + B + 6) +
4 + (8 + 16 * symbols))
(input :: (contents (boolsToSymbols (List.replicate (a (j + 1)) true)), 1 + a (j + 1)) ::
(contents (boolsToSymbols (List.replicate (b (j + 1)) true)), 1 + b (j + 1)) ::
(contents (boolsToSymbols (List.replicate (c (j + 1)) true)), 1 + c (j + 1)) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
(fuel, 1) :: saved) := by sorrySource
Compose the three-counter template compiler, fixed counter strides and reusable unary iteration with the actual inertia-clause encoding.