# Given language consisting Turing machines is decidable or not?

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

• "either A and B" doesn't make sense. Do you mean "both A and B" or "either A or B"? – David Richerby Feb 8 '17 at 11:09
• @DavidRicherby since the answer was accepted, may the question be edited accordingly? – dave Feb 8 '17 at 15:48
• @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. – 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.