Cook–Levin machines: five counter append
ProvedCookLevin.machine_append_one_of_five_counterscomplexitycook-levinloopsturing-machines
Append the unary value of any one of five fixed-position counters to the output while restoring every counter and preserving all other tapes. The chosen selector is fixed when constructing the machine. Runtime is twice the selected value plus three.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_append_one_of_five_counters {k G : Nat} (hk : 7 ≤ k) (hG : 4 ≤ G)
(s : Nat) (hs : s < 5) :
∃ R : Machine, TuringMachine k G R ∧
∀ (a b c d e : Nat) (input : Tape) (bits : List Bool) (saved : List Tape),
saved.length + 7 = k →
let n := if s = 0 then a else if s = 1 then b else if s = 2 then c else if s = 3 then d else e
Transforms R
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate b true)), 1 + b) ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
(contents (boolsToSymbols (List.replicate d true)), 1 + d) ::
(contents (boolsToSymbols (List.replicate e true)), 1 + e) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: saved) (2 * n + 3)
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols (List.replicate b true)), 1 + b) ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
(contents (boolsToSymbols (List.replicate d true)), 1 + d) ::
(contents (boolsToSymbols (List.replicate e true)), 1 + e) ::
(contents (boolsToSymbols (bits ++ List.replicate n true)),
1 + (bits ++ List.replicate n true).length) :: saved) := by sorrySource
Compose the three-counter template compiler, fixed counter strides and reusable unary iteration with the actual inertia-clause encoding.