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.
- 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
