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?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Hint, is $L$ in co-RE? $\endgroup$– John L.May 25, 2019 at 18:41
-
$\begingroup$ yes, I think it is :) thx $\endgroup$– Jon NirMay 26, 2019 at 9:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.