patternMinor
Can the encodings set of a non-trivial class of languages which contains the empty set be recursively enumerable?
Viewed 0 times
canthenonlanguagesemptyrecursivelyenumerabletrivialcontainsencodings
Problem
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$?
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$?
Solution
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:
(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$.
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:
- for any $L_1,L_2 \in RE$, if $L_1 \in S$ and $L_1 \subseteq L_2$ then $L_2 \in S$.
- if $L_1\in S$ then there exists a finite $L_2 \subseteq L_1$ such that $L_2 \in S$.
- 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$.
Context
StackExchange Computer Science Q#2293, answer score: 4
Revisions (0)
No revisions yet.