Membiarkan $C$menjadi seperangkat bahasa enumerable rekursif non-sepele ( ) dan biarkan L menjadi set pengkodean mesin Turing yang mengenali beberapa bahasa dalam C : L = \ {\ langle M \ rangle \ mid L (M) \ dalam C \}$\emptyset \subsetneq C \subsetneq \mathrm{RE}$$L$$C$

Misalkan $\langle M_{loopy}\rangle \in L$ , di mana $M_{loopy}$ adalah TM yang tidak pernah berhenti. Saya ingin tahu apakah mungkin $L \in \mathrm{RE}$ ?

Dengan teorema Rice saya tahu bahwa $L \notin \mathrm{R}$ (himpunan bahasa rekursif), jadi $L \notin \mathrm{RE}$ atau $\overline{L} \notin \mathrm{RE}$ . Apakah itu harus menjadi opsi pertama sejak $M_{loopy} \in L$ ?

Tidak, itu tidak mungkin. Ada versi diperpanjang teorema Rice untuk membuktikan bahwa kumpulan indeks tidak dapat dihitung secara rekursif.

Dalam notasi Anda, teorema menyatakan bahwa jika (non-sepele) $C$ berisi bahasa $L_1$ yang memiliki superset yang tepat $L_2$ tidak masuk$C$, kemudian $L \notin \mathrm{RE}$. Intuisi adalah bahwa tidak ada algoritma yang dapat memisahkan pengkodean$L_1$ dan $L_2$; mereka tidak dapat memutuskan bahwa mesin yang dikodekan tidak menerima sepatah kata pun dari$L_2 \setminus L_1$ setelah waktu yang terbatas, yang harus mereka lakukan.

Sekarang kamu membutuhkan $\emptyset \in C$ tapi $C \neq 2^{\Sigma^*}$, oleh karena itu teorema berlaku dan $L$ tidak dihitung secara rekursif.

1. The Artikel Wikipedia mengerikan, berhati-hatilah!

untuk melengkapi jawaban Raphael, ada perpanjangan teorema Rice yang mengatakan sebagai berikut:

Teorema Padi Umum

Membiarkan $S \subseteq RE$ menjadi properti, dan biarkan $L_S$ semua TM yang memenuhi properti $S$, itu adalah,

$$L_S = \{ \langle M \rangle \mid L(M) \in S \}.$$ Kemudian, $L_S \in RE$jika dan hanya jika semua kondisi berikut berlaku:

1. untuk apa saja $L_1,L_2 \in RE$, jika $L_1 \in S$ dan $L_1 \subseteq L_2$ kemudian $L_2 \in S$.
2. jika $L_1\in S$ maka ada yang terbatas $L_2 \subseteq L_1$ seperti yang $L_2 \in S$.
3. Bahasa 'semua bahasa hingga di $S$'ada di RE.
   (dengan kata lain, ada TM$M_S$ itu, jika $L$ adalah bahasa yang terbatas $L=\{w_1, w_2, \ldots w_k)$, dan $(w_1, w_2, \ldots, w_k)$ diberikan kepada $M_S$ sebagai input, $M$ hanya menerima jika $L\in S$.

Sekarang kembali ke pertanyaan awal. Kita sekarang itu$\langle M_{loopy}\rangle\in L$ begitu $L(\langle M_{loopy}\rangle)\in C$. Tapi$L(\langle M_{loopy}\rangle)=\emptyset$karena TM ini tidak pernah berhenti. Ini artinya$\emptyset \in C$.

Sekarang mari kita lihat kondisi pertama teorema di atas. APAPUN bahasa$L$ memuaskan $\emptyset \subseteq L$. Jadi untuk memenuhi kondisi 1, harus seperti itu$C=RE$. Namun, pertanyaannya menyatakan itu$C\subsetneq RE$ dan karena itu, oleh teorema, $L\notin RE$.

Mungkin saja itu $L$adalah set ulang. Pertimbangkan kopernya$C = RE$. Kemudian$L$adalah himpunan semua kode dari semua mesin Turing. Ini adalah set rekursif, pada kenyataannya, tergantung pada detail pengkodean, kita bisa$L = \mathbb{N}$. Jadi sebenarnya itu salah$L$ tidak bisa rekursif.

Saya curiga Anda salah mengartikan pertanyaan itu.