2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ In your last paragraph:$D'$ accepts $M$ iff $\langle M, M' \rangle$ is not in $L$. You mean that $D$ accepts $\langle M, M' \rangle$ ? Your typical reduction explanation help me to better understand this subject, thanks. $\endgroup$ – Asaf Aug 3 '18 at 14:52
  • 1
    $\begingroup$ @Asaf Yep, $D'$ accepts $M$ if and only if $D$ accepts $\langle M, M' \rangle$ which is the case if and only if $M$ is not in $L$. $\endgroup$ – Daniel Mroz Aug 3 '18 at 14:58

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.