Certificate-sensitive transducer-decider fusion with exact summed clock
OpenCookLevin.transducer_decider_pipeline_generalcompositioncook-levinpolynomial-timeturing-machine
Let a first well-formed multi-tape machine transform an instance and certificate into a bit string within time . Let a second well-formed machine decide a predicate from and a candidate transformed stream within time . Then there is a well-formed fused machine that decides
Pigl(x,w,f(x,w)igr)within exactly steps. Both the transformation and predicate may depend on the original certificate, making this a reusable fusion theorem beyond the certificate-independent corollary.
Preamble
import Definitions.Def_CookLevin_Cost set_option autoImplicit true
Formal statement
namespace CookLevin
/-- General certificate-sensitive transducer/decider fusion. Unlike the unary
pipeline corollary, both the transduced stream and final predicate may depend
on the original certificate. This is the reusable machine-construction layer. -/
theorem transducer_decider_pipeline_general
(f : List Bool → List Bool → List Bool)
(P : List Bool → 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 w)
(M2 : Machine) (k2 G2 : Nat) (hwf2 : TuringMachine k2 G2 M2)
(hdec : ∀ x w y : List Bool,
DecidesIn M2 k2 (boolsToSymbols x) (boolsToSymbols y) (T2 x.length) (P x w 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 w (f x w)) := by
sorry
end CookLevin
Source
General machine-construction layer for CookLevin.transducer_decider_pipeline: https://prove2.me/theorems/4e261916-fcf2-41bb-a7c2-8e5037e3b71b . It strengthens only parameter dependence while preserving the same exact fused-clock obligation.