$$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$ Commented Feb 8, 2017 at 11:09
  • $\begingroup$ @DavidRicherby since the answer was accepted, may the question be edited accordingly? $\endgroup$
    – dave
    Commented Feb 8, 2017 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$ Commented Feb 8, 2017 at 15:53

1 Answer 1


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 and acknowledge you have read our privacy policy.

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