# Prove undecidable and recognizable

Is there a way that I can use If $L=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)=\Sigma^* \big\}$ is in $RE$ or $coRE$ or not in $RE\cup coRE$? to prove that $$L=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_2)\neq\emptyset \big\}$$ is undecidable and recognizable?

• Please don't delete your question after receiving an answer. This can be considered impolite to answerers. Part of our mission is to build up an archive of high-quality questions and answers that will be useful not only to the original asker, but also to others in the future.
– D.W.
Jul 5 at 7:09
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– D.W.
Jul 5 at 7:11

To prove that the language is recognizable simply enumerate all words $$w_1, w_2, \dots,$$ and execute $$L_1$$ and $$L_2$$ on $$w$$ in dovetail fashion (perform one step of $$M_1$$ and $$M_2$$ on $$w_1$$; perform one step of $$M_1$$ and $$M_2$$ on $$w_2$$ and one additional step on $$w_1$$; perform one step of $$M_1$$ and $$M_2$$ on $$w_3$$, one more step on $$w_2$$, and one more step on $$w_1$$; etc). Halt and accept whenever $$M_1$$ or $$M_2$$ accepts.
To prove that the language is not decidable pick $$M_2$$ as the Turing machine that always rejects and notice that $$\langle M_1, M_2 \rangle \in L$$ if and only if $$L(M_1) \neq \emptyset$$. The problem of determining whether a Turing machine accepts at least one word is undecidable (as it can be seen from a simple reduction from the halting problem).