Sea un conjunto no trivial de lenguajes recursivamente enumerables ( ) y L sea ​​el conjunto de codificaciones de máquinas Turing que reconocen algún lenguaje en C : L = \ {\ langle M \ rangle \ mid L (M) \ en C \}$C$$\emptyset \subsetneq C \subsetneq \mathrm{RE}$$L$$C$

Supongamos que , donde es una TM que nunca se detiene. Me pregunto si es posible que ?$\langle M_{loopy}\rangle \in L$$M_{loopy}$$L \in \mathrm{RE}$

Según el teorema de Rice, sé que (el conjunto de lenguajes recursivos), por lo que o . ¿Tiene que ser la primera opción desde ?$L \notin \mathrm{R}$$L \notin \mathrm{RE}$$\overline{L} \notin \mathrm{RE}$$M_{loopy} \in L$

No, eso no es posible. Existe una versión extendida del teorema de Rice para demostrar que un conjunto de índices no es recursivamente enumerable.

En su notación, el teorema establece que si un (no trivial) $C$ contiene un idioma $L_1$ que tiene un superconjunto adecuado $L_2$ no en$C$, entonces $L \notin \mathrm{RE}$. La intuición es que ningún algoritmo puede separar codificaciones de$L_1$ y $L_2$; no pueden decidir que la máquina codificada no acepta ninguna palabra de$L_2 \setminus L_1$ después de un tiempo finito, que tuvieron que hacerlo.

Ahora usted requiere $\emptyset \in C$ pero $C \neq 2^{\Sigma^*}$, por lo tanto, se aplica el teorema y $L$ no es recursivamente enumerable.

1. El artículo de Wikipedia es horrible, ¡cuidado!

Para completar la respuesta de Rafael, hay una extensión del teorema de Rice que dice lo siguiente:

Teorema del arroz generalizado

Dejar $S \subseteq RE$ ser alguna propiedad, y dejar $L_S$ ser todas las TM que satisfacen la propiedad $S$, es decir,

$$L_S = \{ \langle M \rangle \mid L(M) \in S \}.$$ Entonces, $L_S \in RE$si y sólo si todos cumplen las siguientes condiciones:

1. para cualquier $L_1,L_2 \in RE$, Si $L_1 \in S$ y $L_1 \subseteq L_2$ entonces $L_2 \in S$.
2. Si $L_1\in S$ entonces existe un finito $L_2 \subseteq L_1$ tal que $L_2 \in S$.
3. El lenguaje de 'todos los idiomas finitos en $S$'está en RE.
   (en otras palabras, existe una TM$M_S$ eso si $L$ es un lenguaje finito $L=\{w_1, w_2, \ldots w_k)$y $(w_1, w_2, \ldots, w_k)$ se le da a $M_S$ como entrada, $M$ acepta solo si $L\in S$.

Ahora volvamos a la pregunta original. Nosotros ahora que$\langle M_{loopy}\rangle\in L$ entonces $L(\langle M_{loopy}\rangle)\in C$. Pero$L(\langle M_{loopy}\rangle)=\emptyset$ya que este TM nunca se detiene. Esto significa que$\emptyset \in C$.

Ahora veamos la primera condición del teorema anterior. Cualquier idioma$L$ satisface $\emptyset \subseteq L$. Por lo tanto, para satisfacer la condición 1, debe ser que$C=RE$. Sin embargo, la pregunta establece que$C\subsetneq RE$ y por lo tanto, por el teorema, $L\notin RE$.

Es posible que $L$es un re set. Considera el caso$C = RE$. Entonces$L$es el conjunto de todos los códigos de todas las máquinas de Turing. Este es un conjunto recursivo, de hecho, dependiendo de los detalles de la codificación, podríamos tener$L = \mathbb{N}$. Entonces, en realidad es falso que$L$ No puede ser recursivo.

Sospecho que formuló mal la pregunta.