$$L=\{M\mid \text{there exist }x,y\in\Sigma^* \text{ s.t. }x \in L(M)\text{ and } y \notin L(M)\}\,.$$

I think it's not recursively enumerable because this language reduces to complement of the membership problem. $\langle M,w\rangle$ would be input where $y$ would become $w$ and $x$ belongs to $L(M)$.

Please tell me whether I'm correct or not, and help to solve if I'm wrong.

  • 1
    $\begingroup$ "either A and B" doesn't make sense. Do you mean "both A and B" or "either A or B"? $\endgroup$ – David Richerby Feb 8 '17 at 11:09
  • $\begingroup$ @DavidRicherby since the answer was accepted, may the question be edited accordingly? $\endgroup$ – dave Feb 8 '17 at 15:48
  • 1
    $\begingroup$ @dave I guess so. I went ahead and did it, since I have enough rep to edit unilaterally, whereas you'd have to propose the edit and get it accepted. $\endgroup$ – David Richerby Feb 8 '17 at 15:53

In other words, $L=\{\langle M \rangle:L(M)\notin \{\phi,\Sigma^*\}\}$. you can show explicit reduction from a language you already know is not in $RE$. for example $\overline{HP}$ (it is a very standard reduction). or you may use the rice theorem to show that.

I did not understand the reduction you suggested. The reduction from the language you suggested could be as follows: $$f(\langle M \rangle,x)=\langle M_x \rangle$$

$M_x$ on input w:

  1. run $M$ on x for |w| steps.
  2. if $M$ accepted then reject, otherwise accept.

Note that $\epsilon \in L(M_x)$ in anycase, so $L(M_x)\neq \phi$. and $L(M_x)\neq\Sigma^{*}\iff x\in L(M)$. the correctness follows.


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.