Well-formed sequential conjunction construction
OpenCookLevin.turingMachine_and_compose_wfpolynomial-timeturing-machine
Given two well-formed multi-tape Turing machines, there is a well-formed combined machine that returns the conjunction of their verdicts. Whenever the source machines decide in times and , the combined machine decides in the exact summed time . The source well-formedness hypotheses exclude the malformed zero-time counterexamples affecting earlier composition statements.
Preamble
import Definitions.Def_CookLevin_Cost
Formal statement
namespace CookLevin
theorem turingMachine_and_compose_wf
(M1 M2 : Machine) (k1 k2 G1 G2 : Nat)
(hwf1 : TuringMachine k1 G1 M1) (hwf2 : TuringMachine k2 G2 M2) :
∃ (M : Machine) (k G : Nat),
TuringMachine k G M ∧
∀ (xs ws : List Symbol) (t1 t2 : Nat) (b1 b2 : Bool),
DecidesIn M1 k1 xs ws t1 b1 →
DecidesIn M2 k2 xs ws t2 b2 →
DecidesIn M k xs ws (t1 + t2) (b1 && b2) := by sorry
end CookLevinSource