0
$\begingroup$

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?

$\endgroup$
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.
    Jul 5 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.
    Jul 5 at 7:11
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.