Well-formed transducer-comparator composition core
OpenCookLevin.transducer_comparator_compose_corepolynomial-timesat-verifierturing-machine
Retired because this proposed core duplicated CookLevin.transducer_comparator_compose instead of isolating a genuinely smaller tape-routing obligation.
Preamble
import Definitions.Def_CookLevin_Verifier
Formal statement
namespace CookLevin
theorem transducer_comparator_compose_core
(c1 : Nat) (M1 : Machine) (k1 G1 : Nat) (hwf1 : TuringMachine k1 G1 M1)
(htrans : ∀ x w : List Bool,
(execute M1 (startConfig2 k1 (boolsToSymbols x) (boolsToSymbols w)) (c1 * (x.length + 1) ^ 2)).1 = M1.length ∧
outputOf k1 (execute M1 (startConfig2 k1 (boolsToSymbols x) (boolsToSymbols w)) (c1 * (x.length + 1) ^ 2))
(c1 * (x.length + 1) ^ 2 + 2) = encodeFormula (decodeFormula x))
(c2 : Nat) (M2 : Machine) (k2 G2 : Nat) (hwf2 : TuringMachine k2 G2 M2)
(hcomp : ∀ x y : List Bool,
DecidesIn M2 k2 (boolsToSymbols x) (boolsToSymbols y)
(c2 * (x.length + 1)) (decide (y = x))) :
∃ (M : Machine) (k G : Nat),
TuringMachine k G M ∧
∀ x w : List Bool,
DecidesIn M k (boolsToSymbols x) (boolsToSymbols w)
(c1 * (x.length + 1) ^ 2 + c2 * (x.length + 1))
(decide (encodeFormula (decodeFormula x) = x)) := by sorry
end CookLevinSource