Cook–Levin machines: trim unary prefix at its end
ProvedCookLevin.machine_trim_unary_from_endcomplexitycook-levinloopsturing-machines
From a selected work tape head at n+2, move left and clear cell n+1, preserving every other cell, tape and head. This two-step machine shortens a nonempty unary prefix by one when invoked at its terminator. No assumption on other contents is needed.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_trim_unary_from_end {k G j : Nat} (hk : 2 ≤ k)
(hG : 4 ≤ G) (hj : 0 < j) :
∃ R : Machine, TuringMachine k G R ∧
∀ (n : Nat) (f : Nat → Symbol) (left right : List Tape), left.length = j →
Transforms R (left ++ (f, n + 2) :: right) 2
(left ++ ((fun p => if p = n + 1 then blankSymbol else f p), n + 1) :: right) := by sorrySource
Compose the three-counter template compiler, fixed counter strides and reusable unary iteration with the actual inertia-clause encoding.