Cook–Levin machines: next counter
ProvedCookLevin.machine_inertia_next_counter_from_positionscomplexitycook-levinloopsturing-machines
Construct the exact initial next-time-cell literal counter from reusable unary position fuel and fixed logical tape and symbol bounds. Add one extra stride for the unused position radix entry, preserve the fuel and all other tapes, and give an explicit linear runtime.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_inertia_next_counter_from_positions {k G : Nat} (hk : 6 ≤ k)
(hG : 4 ≤ G) (tapes symbols : Nat) :
∃ R : Machine, TuringMachine k G R ∧
∀ (n : Nat) (input head cell out : Tape) (fuel : Nat → Symbol) (saved : List Tape),
fuel 0 ≠ oneSymbol →
(∀ i, i < n → fuel (1 + i) = oneSymbol) →
fuel (1 + n) ≠ oneSymbol →
let c := 8 * symbols * tapes * (n + 1) + 1
Transforms R
(input :: head :: cell :: (contents [], 1) :: out :: (fuel, 1) :: saved)
(8 * symbols * tapes + 1 + n * (8 * symbols * tapes + 6) + 4)
(input :: head :: cell ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
out :: (fuel, 1) :: saved) := by sorrySource
Compose the three-counter template compiler, fixed counter strides and reusable unary iteration with the actual inertia-clause encoding.