Cook–Levin machines: canonical bit copy from a work bank
ProvedCookLevin.machine_copy_bits_from_bankcomplexitycook-levinloopsturing-machines
A well-formed Turing machine copies a computed bit prefix from the penultimate tape to a fresh final tape in bits.length+3 steps. The input and preceding work bank are preserved. Both source and destination begin at head zero and end just after the bits. The destination is canonical, including the start marker and blank tail; the source may have arbitrary marker and tail beyond its non-bit terminator.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_copy_bits_from_bank {a G : Nat} (hG : 4 ≤ G) :
∃ R : Machine, TuringMachine (a + 3) G R ∧
∀ (bits : List Bool) (input : Tape) (f : Nat → Symbol) (saved : List Tape),
saved.length = a →
(∀ j, (hj : j < bits.length) → f (1 + j) = boolSym (bits[j])) →
(¬ (f (1 + bits.length) = zeroSymbol ∨ f (1 + bits.length) = oneSymbol)) →
Transforms R (input :: (saved ++ [(f, 0), (contents [], 0)])) (bits.length + 3)
(input :: (saved ++ [(f, 1 + bits.length),
(contents (boolsToSymbols bits), 1 + bits.length)])) := by sorrySource
Apply the accepted canonical copy-from-zero machine under a tape permutation that leaves the input index fixed.