# Is the language of all TMs *not* accepting a given string, Enumerable?

Is the following language in RE?
$$L = \{\langle M\rangle : M\text{ is a TM that does not accept }010\}$$

I could use Rice's Theorem with the property $$P = \{L : 010\text{ is not in }L\}$$ to show it isn't in R, but how do I show it is in RE?

• Hint, is $L$ in co-RE? – John L. May 25 '19 at 18:41
• yes, I think it is :) thx – Jon Nir May 26 '19 at 9:52

The classic technique of dovetailing can be used to show the complement of $$L$$, $$\{\langle M\rangle : M\text{ is a TM that accept }010\}$$ is recursively enumerable. Check this answer for details.
Since $$L$$ is not decidable as shown by Rice's theorem, $$L$$ cannot be recursively enumerable.
Exercise. Show that $$\{\langle M\rangle : M\text{ is a TM that accept } 010\text{ and }101\}$$ is not in RE.