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?
2
-
$\begingroup$ 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. $\endgroup$– D.W. ♦Commented Jul 5, 2021 at 7:09
-
$\begingroup$ 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! $\endgroup$– D.W. ♦Commented Jul 5, 2021 at 7:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
