什么都不接受的图灵机如何不是递归可枚举的？
How is Turing Machine which accepts nothing is not Recursively Enumerable?
不接受任何东西的图灵机为什么不是递归可枚举的。
我们将使用间接论证来证明不接受任何内容的图灵机编码语言不能递归枚举。
引理1：如果L及其补码是递归可枚举的，则L是递归的。
证明：令M为枚举L的TM，M'为枚举L的补码的TM。给定任意字符串s，我们可以判断s是否在L 如下。开始 运行 M 和 M'，交错执行，以便每个最终都获得任意数量的运行时间。如果 s 在 L 中，M 最终会列出它，此时我们知道 s 在 L 中并且我们停止接受。如果 s 不在 L 中，M' 将最终列出它，此时我们知道 s 不在 L 中并且我们停止拒绝。因此，对于任何 s，如果 s 在 L 中，我们可以停止接受，否则停止拒绝。因此，L及其补码是递归的。
引理 2: 接受某物的图灵机编码语言是递归可枚举的。
证明：所有图灵机编码的集合是可数的，所有可能的磁带输入的集合也是可数的。因此，机器和输入对的集合 (M, s) 是可数的。因此，我们可以假设这些对 p1, p2, ..., pk, ... ..., pk, ... 所以每个人最终都会获得任意数量的运行时间。如果 pk 进入 halt-accept 状态，我们可以立即将 M 列为接受某物（即相应的 s）的 TM，我们甚至可以终止所有其他 运行 检查相同 M 的实例（并放弃启动任何新的）。接受某些输入的任何机器 M 最终都将启动并最终停止接受输入，因此所有机器最终都会被枚举。
引理 3: 什么都不接受的图灵机编码语言不是递归的。
证明：这是莱斯定理的直接结果。 属性 "accepts nothing" 是语言本身的语义 属性 并且对某些但不是所有语言都是正确的；因此，没有 TM 可以决定另一个 TM 是否接受带有 属性 的语言。
定理：不接受任何东西的图灵机编码语言不可递归枚举。
证明：假设这种语言是递归可枚举的。我们已经在引理 2 中证明了它的补集是递归可枚举的。那么，根据引理 1，两种语言都是递归的。然而，引理 3 证明了该语言不是递归的。这是一个矛盾。唯一的假设是该语言是递归可枚举的，因此该假设一定是错误的：因此该语言不是递归可枚举的。
不接受任何东西的图灵机为什么不是递归可枚举的。
我们将使用间接论证来证明不接受任何内容的图灵机编码语言不能递归枚举。
引理1：如果L及其补码是递归可枚举的，则L是递归的。
证明：令M为枚举L的TM，M'为枚举L的补码的TM。给定任意字符串s，我们可以判断s是否在L 如下。开始 运行 M 和 M'，交错执行，以便每个最终都获得任意数量的运行时间。如果 s 在 L 中，M 最终会列出它，此时我们知道 s 在 L 中并且我们停止接受。如果 s 不在 L 中，M' 将最终列出它，此时我们知道 s 不在 L 中并且我们停止拒绝。因此，对于任何 s，如果 s 在 L 中，我们可以停止接受，否则停止拒绝。因此，L及其补码是递归的。
引理 2: 接受某物的图灵机编码语言是递归可枚举的。
证明：所有图灵机编码的集合是可数的，所有可能的磁带输入的集合也是可数的。因此，机器和输入对的集合 (M, s) 是可数的。因此，我们可以假设这些对 p1, p2, ..., pk, ... ..., pk, ... 所以每个人最终都会获得任意数量的运行时间。如果 pk 进入 halt-accept 状态，我们可以立即将 M 列为接受某物（即相应的 s）的 TM，我们甚至可以终止所有其他 运行 检查相同 M 的实例（并放弃启动任何新的）。接受某些输入的任何机器 M 最终都将启动并最终停止接受输入，因此所有机器最终都会被枚举。
引理 3: 什么都不接受的图灵机编码语言不是递归的。
证明：这是莱斯定理的直接结果。 属性 "accepts nothing" 是语言本身的语义 属性 并且对某些但不是所有语言都是正确的；因此，没有 TM 可以决定另一个 TM 是否接受带有 属性 的语言。
定理：不接受任何东西的图灵机编码语言不可递归枚举。
证明：假设这种语言是递归可枚举的。我们已经在引理 2 中证明了它的补集是递归可枚举的。那么，根据引理 1，两种语言都是递归的。然而，引理 3 证明了该语言不是递归的。这是一个矛盾。唯一的假设是该语言是递归可枚举的，因此该假设一定是错误的：因此该语言不是递归可枚举的。