# Is the language containing Turing machine $(M_1, M_2)$ such that $L(M_1) \cup L(M_2) = \Sigma^*$ decidable?

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.

• What are $M_1$ and $M_2$? The question is unclear, please define precisely "the resulting language". And if this is an exercise, please transliterate the exact wording. Nov 23, 2021 at 19:34
• I have edited your question. Please check if it matches what you intended to ask. Also it is still unclear what $E_{TM}$ is and how reducing to (and not from) another language would help to prove that your language is undecidable. Nov 23, 2021 at 20:43

## 1 Answer

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^*$$.

• Good job on understanding what the question was! Nov 23, 2021 at 20:21