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

Improve this question
$\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, 2012 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, 2012 at 22:39
  • $\begingroup$ You mean "so either $L \notin \mathrm{RE}$ or $\overline{L} \notin \mathrm{RE}$", I assume? $\endgroup$
    – Raphael ♦
    Jun 8, 2012 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, 2012 at 22:55
  • $\begingroup$ @Raphael, you are right. $\endgroup$
    – Numerator
    Jun 9, 2012 at 8:30

3 Answers 3

Reset to default
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!
Improve this answer
$\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, 2012 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, 2012 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$.

Improve this answer
$\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, 2018 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, 2018 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, 2019 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, 2019 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The OP excluded $\mathrm{RE}$. $\endgroup$
    – Raphael ♦
    Jun 8, 2012 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, 2012 at 22:45
  • $\begingroup$ @Andrej Thank you for the answer, but Raphael is right, I excluded $RE$. $\endgroup$
    – Numerator
    Jun 9, 2012 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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