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

Problem Detail: 

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

Asked By : Numerator

Answered By : Raphael

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!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2293

 Ask a Question

 Download Related Notes/Documents