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

|cite|improve this question
$\endgroup$
  • 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!
|cite|improve this answer
$\endgroup$
  • $\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$.

|cite|improve this answer
$\endgroup$
  • $\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 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 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.

|cite|improve this answer
$\endgroup$
  • $\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♦ 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.