Cook–Levin machines: canonical output of a bounded computation
ProvedCookLevin.machine_canonical_output_transformscomplexitycook-levinloopsturing-machines
Every bounded standard-input computation can be followed by a fresh canonical output copy, preserving the original input and work contents. The copied tape has the exact encoded bit contents, start marker and blank suffix. The machine uses one additional tape and runs in at most twice the original time plus output length plus four steps.
Preamble
import Definitions.Def_CookLevin_Cost import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_canonical_output_transforms {k G : Nat} (M : Machine)
(hM : TuringMachine k G M) (T : Nat → Nat) (f : List Bool → List Bool)
(hcomp : ComputesInTime M k T f) :
∃ R : Machine, TuringMachine (k + 1) G R ∧
∀ x, ∃ (input : Tape) (saved : List Tape), saved.length = k - 1 ∧
Transforms R (startConfig2 (k + 1) (boolsToSymbols x) []).2
(2 * T x.length + (f x).length + 4)
(input :: (saved ++ [(contents (boolsToSymbols (f x)), 1 + (f x).length)])) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.