Cook–Levin machines: append one of three unary counters
ProvedCookLevin.machine_append_one_of_three_counterscomplexitycook-levinloopsturing-machines
For a fixed selector among three unary counters, a well-formed Turing machine appends that counter value to the canonical output in exactly the stated bound of 2*n+3 steps. All three counter contents and heads, the input tape, and the saved work tapes are preserved. The construction works for every counter value and output prefix.
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_three_counters {k G : Nat} (hk : 5 ≤ k) (hG : 4 ≤ G)
(s : Nat) (hs : s < 3) :
∃ R : Machine, TuringMachine k G R ∧
∀ (a b c : Nat) (input : Tape) (bits : List Bool) (saved : List Tape),
saved.length + 5 = k →
let n := if s = 0 then a else if s = 1 then b else c
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 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 (bits ++ List.replicate n true)),
1 + (bits ++ List.replicate n true).length) :: saved) := by sorrySource
Apply the accepted restoring unary append machine under a selector-dependent tape permutation fixing the input index.