We are given two Turing machines $M_1$ and $M_2$ and we wish to decide whether the union of the language $L(M_1)$ accepted by $M_1$ with the language $L(M_2)$ accepted by $M_2$ coincides with $\Sigma^*$.
Is this problem undecidable? In other words, is the language $\{ (M_1, M_2) \mid L(M_1) \cup L(M_2) = \Sigma^*\} $ undecidable?
I'm thinking about doing a proof by contradiction and somehow reducing to $E_{TM}$, but not sure where to start.
Yes, the language $L = \{ (M_1, M_2) \mid L(M_1) \cup L(M_2) = \Sigma^* \}$, where $M_1$ and $M_2$ are Turing machines, is undecidable.
If $L$ were decidable then you would be able to decide if the language accepted by a Turing machine $T$ is $\Sigma^*$ by simply checking whether $(T,T) \in L$.
To see that the problem of deciding whether a given Turing machine $T$ satisfies $L(T) = \Sigma^*$ is undecidable you can reduce from the well-known undecidable problem of deciding whether a given Turing machine $M$ halts on empty input. To do so, it suffices to construct $T$ from $M$ by replacing each transition that halts the machine and rejects with a transition that halts the machine and accepts. Then $M$ halts if and only if $L(T)=\Sigma^*$.
