Can the encodings set of a non-trivial class of languages which contains the empty set be recursively enumerable?

Question

Let $C$ be a non-trivial set of recursively enumerable languages ($\emptyset \subsetneq C \subsetneq \mathrm{RE}$) and let $L$ be the set of encodings of Turing machines that recognize some language in $C$: $$L=\{\langle M \rangle \mid L(M) \in C \}$$

Suppose that $\langle M_{loopy}\rangle \in L$, where $M_{loopy}$ is a TM that never halts. I wonder if it is possible that $L \in \mathrm{RE}$?

By Rice's theorem I know that $L \notin \mathrm{R}$ (the set of recursive languages), so either $L \notin \mathrm{RE}$ or $\overline{L} \notin \mathrm{RE}$. Does it have to be the first option since $M_{loopy} \in L$?

Answer 1

No, that is not possible. There is an extended version of Rice's theorem¹ to prove an index set is not recursively enumerable.

In your notation, the theorem states that if a (non-trivial) $C$ contains a language $L_1$ which has a proper superset $L_2$ not in $C$, then $L \notin \mathrm{RE}$. The intuition is that no algorithm can separate encodings of $L_1$ and $L_2$; they can not decide that the encoded machine does not accept any word from $L_2 \setminus L_1$ after a finite amount of time, which they had to.

Now you require $\emptyset \in C$ but $C \neq 2^{\Sigma^*}$, therefore the theorem applies and $L$ is not recursively enumerable.

---

1. The Wikipedia article is horrible, beware!

Answer 2

to complete Raphael's answer, there is an extension of Rice's theorem that says the following:

Generalized Rice's Theorem

Let $S \subseteq RE$ be some property, and let $L_S$ be all the TMs that satisfy the property $S$, that is, $$L_S = \{ \langle M \rangle \mid L(M) \in S \}.$$ Then, $L_S \in RE$ if and only if all the following conditions hold:

1. for any $L_1,L_2 \in RE$, if $L_1 \in S$ and $L_1 \subseteq L_2$ then $L_2 \in S$.
2. if $L_1\in S$ then there exists a finite $L_2 \subseteq L_1$ such that $L_2 \in S$.
3. The language of 'all finite languages in $S$' is in RE.
   (in other words, there exists a TM $M_S$ that, if $L$ is a finite language $L=\{w_1, w_2, \ldots w_k)$, and $(w_1, w_2, \ldots, w_k)$ is given to $M_S$ as an input, $M$ accepts only if $L\in S$.

Now back to the original question. We now that $\langle M_{loopy}\rangle\in L$ so $L(\langle M_{loopy}\rangle)\in C$. But $L(\langle M_{loopy}\rangle)=\emptyset$ since this TM never halts. This means that $\emptyset \in C$.

Now lets look on the first condition of the above theorem. ANY language $L$ satisfies $\emptyset \subseteq L$. Thus in order to satisfy condition 1, it must be that $C=RE$. However, the question states that $C\subsetneq RE$ and therefore, by the theorem, $L\notin RE$.

Answer 3

It is possible that $L$ is an r.e. set. Consider the case $C = RE$. Then $L$ is the set of all codes of all Turing machines. This is a recursive set, in fact, depending on the details of the encoding, we could have $L = \mathbb{N}$. So it is actually false that $L$ cannot be recursive.

I suspect you misformulated the question.