可以递归枚举包含空集的非平凡语言类的编码集吗？

Question

令$ c $是一组非平凡的枚举语言（$ emptyset subsetneq c subsetneq subsetneq subsetneq mathrm {re} $），让$ l $是一组通知某些语言的Turing Machines $：$$ l = { langle m rangle mid l（m） in C } $$

假设$ langle m_ {loopopy} rangle in L $，其中$ m_ {loopopy} $是一个永不停止的TM。我想知道是否有可能在 mathrm {re} $中$ l ？

由赖斯的定理我知道，$ l notin mathrm {r} $（递归语言的集合），所以要么$ l notin notin mathrm {re} $或$ overline {l} notin notin mathrm {re} $。这必须是$ m_ {loopopy} in L $的第一个选项？

Answer 1

不，那是不可能的。有一个扩展版本的稻米定理，以证明索引集并非递归地枚举。

在您的符号中，定理指出，如果（非平凡）$ c $包含具有适当超级$ L_2 $的语言$ L_1 $ 不是 在$ c $中，然后$ l notin mathrm {re} $。直觉是，没有算法可以分开$ L_1 $和$ L_2 $的编码；他们无法决定编码的机器确实 不是 在有限的时间之后，接受$ l_2 setminus l_1 $的任何单词，他们必须要这样做。

现在，您需要$ emptyset 在c $中，但是$ c neq 2^{ sigma^*} $，因此，定理适用，$ l $又不递归地枚举。

---

1. 这 维基百科文章 可怕，当心！

Answer 2

为了完成拉斐尔的回答，赖斯定理的延伸说：

大米定理

令$ s subseteq re $为某些属性，让$ l_s $为满足属性$ s $的所有tms，也就是说，$$ l_s = { langle m rangle rangle rangle mid l（m） in s }。 全部 以下条件保持：

1. 对于任何$ L_1，L_2 in Re $，如果$ L_1 在S $中，$ L_1 subseteq l_2 $ the $ l_2 in S $。
2. 如果$ l_1 在s $中，则存在有限的$ l_2 subseteq l_1 $，因此$ l_2 in s $。
3. “ $ s $中的所有有限语言”的语言在于。
   （换句话说，存在一个tm $ m_s $，如果$ l $是有限语言$ l = {w_1，w_2，w_2， ldots w_k）$和$（w_1，w_1，w_2， ldots，w_k）$仅作为输入给出$ m_s $，$ m $仅在$ l in s $中接受。

现在回到原始问题。我们现在，$ langle m_ {loopopy} rangle in l $ so $ s o $ l（ langle m_ {loopopy} rangle） in C $。但是$ l（ langle m_ {loopopy} rangle）= emptyset $，因为此tm永远不会停止。这意味着C $中的$ emptyset 。

现在，让我们看看上述定理的第一个条件。 任何 语言$ l $满足$ emptyset subseteq l $。因此，为了满足条件1，必须是$ c = re $。但是，问题指出，$ c subsetneq re $ $，因此，根据定理，$ l notin re $。

Answer 3

$ l $可能是重新设置。考虑案例$ c = re $。然后，$ l $是所有图灵机的所有代码的集合。实际上，这是一个递归集，具体取决于编码的详细信息，我们可以拥有$ l = mathbb {n} $。因此，$ l $不能递归是错误的。

我怀疑您错误地提出了这个问题。