Question

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

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top