8
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ You should explain your notation. What is $\langle M \rangle$? What is $L(M)$? What is $\overline{L}$? The only thing you explained was what RE stands for, and that's the one thing you need not explain. $\endgroup$ – Andrej Bauer Jun 8 '12 at 21:59
  • 2
    $\begingroup$ @AndrejBauer: That is fairly standard notation. They mean, from left to right, the encoding of M, the language accepted by $M$, and the complement of $L$. $\endgroup$ – Raphael Jun 8 '12 at 22:39
  • $\begingroup$ You mean "so either $L \notin \mathrm{RE}$ or $\overline{L} \notin \mathrm{RE}$", I assume? $\endgroup$ – Raphael Jun 8 '12 at 22:48
  • 1
    $\begingroup$ there is an extension of Rice's theorem that describes the conditions that make $L\in RE$. I might have time later to write it, unless others do. BUT, if $\emptyset\in C$ (which is implied by the existence of $M_{loop}\in L$), then $L\notin RE$. This also follows from Rice's thm with the standard proof. $\endgroup$ – Ran G. Jun 8 '12 at 22:55
  • $\begingroup$ @Raphael, you are right. $\endgroup$ – Numerator Jun 9 '12 at 8:30
3
$\begingroup$

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!
$\endgroup$
2
  • $\begingroup$ Can I claim that since $L(M_{loop})= \emptyset$ we get that the Empty turing machine, which doesn't accept any word $Etm \subset L$ and due to Rice Theorem we know that $L \notin R$ (all Rice conditions are OK) so because $Etm \in Co-RE$ we get that $L \notin RE$ ? $\endgroup$ – Numerator Jun 13 '12 at 15:20
  • $\begingroup$ @Numerator: What is Etm? In any case, $L$ is not necessarily in $\mathsf{co\text{-}RE}$, so no. If it was, that reasoning would work, yes. $\endgroup$ – Raphael Jun 13 '12 at 20:16
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Is there a source where I can learn more about this theorem? I couldn't find one online which was satisfactory. $\endgroup$ – Gokul Sep 18 '18 at 5:10
  • 1
    $\begingroup$ @Gokul I am told that this theorem appears in the book of Hopcroft, Motwani, Ullman, but only in its first version (apparently it was removed in later versions). $\endgroup$ – Ran G. Sep 18 '18 at 12:04
  • $\begingroup$ @Ran G. I couldn't find the mentioned book to check this but #3 seems wrong, since for $S=RE$, the language of all finite languages is not $RE$. You might rather mean another similar condition: $\forall x (x \in L_S \iff \exists u(D_{f(u)} \subseteq W_x))$, where $D$ is the canonical coding of finite languages, $W$ the standard enumeration of $RE$ languages, and $f$ some totally computable function. In that case, this condition is solely equivalent to $L_S$ being $RE$. (See H. Rogers Theory of Recursive Functions and Effective Computability p324) Although #1 and #2 are sufficient here. $\endgroup$ – Beleg Jan 6 '19 at 12:36
  • $\begingroup$ @Beleg I don't see why it is wrong. If $S=RE$ then any finite language is in $S$, hence the TM that accepts any string (or rather, any well-formatted string) is a decider for the set of all finite languages in S. If you still disagree, let's continue in the Computer Science Chat. $\endgroup$ – Ran G. Jan 6 '19 at 17:44
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The OP excluded $\mathrm{RE}$. $\endgroup$ – Raphael Jun 8 '12 at 22:41
  • $\begingroup$ @Raphael I'm not sure (it depends whether $\subset$ was intended as strict), but if it's what makes the question interesting, let's assume $C$ is not the whole of $\mathrm{RE}$. $\endgroup$ – Gilles 'SO- stop being evil' Jun 8 '12 at 22:45
  • $\begingroup$ @Andrej Thank you for the answer, but Raphael is right, I excluded $RE$. $\endgroup$ – Numerator Jun 9 '12 at 8:26

Your Answer

By clicking ā€œPost Your Answerā€, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.