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$?

Question

I tried to solve it as the following: $$\overline{L}=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)\neq\Sigma^* \big\}$$ I'll show that $\overline{L}\not\in RE$ by reduction from $$\overline{A_{TM}} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ rejects } w \big\}$$ I begin by assuming that $\overline{L}$ is recognized by some TM $M'$.

Next, I construct a machine $M_{\overline{A_{TM}}}$ that will use $M'$ to recognize $\overline{A_{TM}}$.

TM $M'$ on input $\langle M, w\rangle$:

1. Build TM $M_1,M_2$

2. Simulate $M_1,M_2$ on all $x\in\Sigma^*$, Any simulation will be at most $|x|$ steps.

3. If $M_1$ and $M_2$ reject the same $x$, then $M'$ will accept $\langle M, w\rangle$.

4. If $M_1$ or $M_2$ accept some $x$, then $M'$ will reject $\langle M, w\rangle$.

Therefore, $\langle M, w \rangle\in\overline{A_{TM}}$ exactly when $\langle M_1,M_2\rangle\in\overline{L}$.

Because $\overline{A_{TM}}\not\in RE$ so is $\overline{L}$, then $L\not\in co-RE$

Is it true and can I use similar approach to show that $L\not\in RE$?

Thanks.

Answer 1

Your proof is not very clear to me. In your description of $M'$ I don't understand what $M_1$ and $M_2$ are, or why they have the properties you claim they do.

A typical reduction proof looks like:

1. You have some language $L$ which you wish to prove is, say, not $RE$.
2. You have a language $L'$ which you know is not $RE$.
3. Suppose there exists a TM $D$ which recognizes $L$
4. Construct a TM $D'$ to recognize $L'$. Usually $D'$ will take some input $x$ and transform it into an input $y$ for $D$, such that $D'$ accepts $x$ if and only if $D$ accepts $y$

So let's do the same thing for this problem. We'll reduce $TOTAL$ (which is neither $RE$ nor $co-RE$) to $L$.

Suppose $D$ recognizes $L$. Let $D'$ be the TM:

TM $D'$ on input $\langle M \rangle$:

1. Let $M'$ be the TM that acts as $M$ but inverts the output
2. Run $D$ on $\langle M, M' \rangle$
3. Accept if $D$ accepts, reject if $D$ rejects.

Now we want to prove that $D'$ recognizes $TOTAL$. This is straightforward. $\langle M, M' \rangle$ is in $L$ if and only if $L(M) \cup L(M') = \Sigma^*$. But $L(M') = \overline{L(M)}$. So $D'$ accepts $M$ if and only if $M$ either accepts or rejects every input, which is precisely what it means for $M$ to be in $TOTAL$!

So we have shown that no TM can recognize $L$, so $L$ isn't $RE$.

To show that it's not $co-RE$ either we take $D$ to recognize $\bar{L}$ instead, and define $D'$ just as above. So now $D'$ accepts $M$ if and only if $\langle M, M' \rangle$ is not in $L$. The same argument above shows us this is exactly true when $M$ is not in $TOTAL$.