Cook–Levin machines: halt next-time counters
ProvedCookLevin.machine_halt_next_counters_from_positionscomplexitycook-levinloopsturing-machines
Construct both next-time head and cell literal counters from reusable unary position fuel, including the unused radix entry, with 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_halt_next_counters_from_positions {k G : Nat} (hk : 8 ≤ k)
(hG : 4 ≤ G) (tapes symbols : Nat) :
∃ R : Machine, TuringMachine k G R ∧
∀ (n : Nat) (input state 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 * tapes * (n + 1) + 3
let e := 8 * symbols * tapes * (n + 1) + 1
Transforms R
(input :: state :: head :: (contents [], 1) :: cell :: (contents [], 1) :: out :: (fuel, 1) :: saved)
(8 * tapes + 8 * symbols * tapes + 8 + n * (8 * tapes + 8 * symbols * tapes + 6))
(input :: state :: head ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) :: cell ::
(contents (boolsToSymbols (List.replicate e true)), 1 + e) ::
out :: (fuel, 1) :: saved) := by sorrySource
Compose the five-counter template compiler, fixed counter strides and reusable unary iteration with the actual halt-clause encoding.