Generic transducer-decider pipeline
OpenCookLevin.transducer_decider_pipelinepolynomial-timeturing-machine
A transducer whose output depends only on the instance can be pipelined into a two-input Boolean decider. If the transducer runs in time and the decider runs in time , the pipeline decides the predicate on the instance and the transduced output in time . This reusable statement isolates the tape-routing and control-state construction from any particular encoding or predicate.
Preamble
import Definitions.Def_CookLevin_Cost
Formal statement
namespace CookLevin
theorem transducer_decider_pipeline
(f : List Bool → List Bool) (P : List Bool → List Bool → Bool)
(T1 T2 : Nat → Nat)
(M1 : Machine) (k1 G1 : Nat) (hwf1 : TuringMachine k1 G1 M1)
(htrans : ∀ x w : List Bool,
(execute M1 (startConfig2 k1 (boolsToSymbols x) (boolsToSymbols w)) (T1 x.length)).1 = M1.length ∧
outputOf k1 (execute M1 (startConfig2 k1 (boolsToSymbols x) (boolsToSymbols w)) (T1 x.length))
(T1 x.length + 2) = f x)
(M2 : Machine) (k2 G2 : Nat) (hwf2 : TuringMachine k2 G2 M2)
(hdec : ∀ x y : List Bool,
DecidesIn M2 k2 (boolsToSymbols x) (boolsToSymbols y) (T2 x.length) (P x y)) :
∃ (M : Machine) (k G : Nat),
TuringMachine k G M ∧
∀ x w : List Bool,
DecidesIn M k (boolsToSymbols x) (boolsToSymbols w)
(T1 x.length + T2 x.length) (P x (f x)) := by sorry
end CookLevinSource
Standard sequential composition principle for the Cook-Levin multi-tape machine model.