Soit un ensemble non trivial de langages récursivement énumérables ( ) et soit L l'ensemble des encodages des machines Turing qui reconnaissent un langage en C : L = \ {\ langle M \ rangle \ mid L (M) \ in C \}$C$$\emptyset \subsetneq C \subsetneq \mathrm{RE}$$L$$C$

Supposons que $\langle M_{loopy}\rangle \in L$ , où $M_{loopy}$ est une MT qui ne s'arrête jamais. Je me demande s'il est possible que $L \in \mathrm{RE}$ ?

Par le théorème de Rice, je sais que $L \notin \mathrm{R}$ (l'ensemble des langages récursifs), donc soit $L \notin \mathrm{RE}$ ou $\overline{L} \notin \mathrm{RE}$ . Doit-il être la première option depuis $M_{loopy} \in L$ ?

Non, ce n'est pas possible. Il existe une version étendue du théorème de Rice¹ pour prouver qu'un ensemble d'index n'est pas récursivement énumérable.

Dans votre notation, le théorème déclare que si un (non trivial) contient un langage qui a un sur-ensemble approprié pas en , alors . L'intuition est qu'aucun algorithme ne peut séparer les codages de et ; ils ne peuvent pas décider que la machine ne encodée pas accepter un mot de après un certain laps de temps fini, qu'ils devaient.$C$$L_1$$L_2$ $C$$L \notin \mathrm{RE}$$L_1$$L_2$$L_2 \setminus L_1$

Vous avez maintenant besoin de mais , donc le théorème s'applique et n'est pas récursivement énumérable.$\emptyset \in C$$C \neq 2^{\Sigma^*}$$L$

1. L' article Wikipedia est horrible, méfiez-vous!

pour compléter la réponse de Raphaël, il y a une extension du théorème de Rice qui dit ce qui suit:

Théorème de Rice généralisé

Soit une propriété et Soit toutes les MT qui satisfont la propriété , c'est-à-dire Ensuite, si et seulement si toutes les conditions suivantes sont réunies:$S \subseteq RE$$L_S$$S$

$$L_S = \{ \langle M \rangle \mid L(M) \in S \}.$$ $L_S \in RE$

1. pour toute $L_1,L_2 \in RE$, si $L_1 \in S$ et $L_1 \subseteq L_2$ puis $L_2 \in S$.
2. si $L_1\in S$ alors il existe un fini $L_2 \subseteq L_1$ tel que $L_2 \in S$.
3. La langue de «toutes les langues finies en $S$'est en RE.
   (en d'autres termes, il existe une MT$M_S$ que si $L$ est une langue finie $L=\{w_1, w_2, \ldots w_k)$, et $(w_1, w_2, \ldots, w_k)$ est donné à $M_S$ en entrée, $M$ accepte uniquement si $L\in S$.

Revenons maintenant à la question d'origine. Nous maintenant$\langle M_{loopy}\rangle\in L$ donc $L(\langle M_{loopy}\rangle)\in C$. Mais$L(\langle M_{loopy}\rangle)=\emptyset$puisque cette TM ne s'arrête jamais. Cela signifie que$\emptyset \in C$.

Voyons maintenant la première condition du théorème ci-dessus. N'IMPORTE QUELLE langue$L$ satisfait $\emptyset \subseteq L$. Ainsi, pour satisfaire à la condition 1, il faut que$C=RE$. Cependant, la question indique que$C\subsetneq RE$ et donc, par le théorème, $L\notin RE$.

Il est possible que $L$est un re set. Considérez le cas$C = RE$. alors$L$est l'ensemble de tous les codes de toutes les machines Turing. Ceci est un ensemble récursif, en fait, selon les détails de l'encodage, nous pourrions avoir$L = \mathbb{N}$. Il est donc faux que$L$ ne peut pas être récursif.

Je soupçonne que vous avez mal formulé la question.