我有一个来自理论计算机科学领域的问题。
所谓的通用语言 L_u 是由对 (M, w) 组成的，使得 w \in L(M)。语言 L_ne 由具有非空语言的机器 M（实际上是它们的描述，但我们在这里不要太拘谨）组成。我们都知道 L_u 和 L_ne 都是非递归的，但仍然是 RE（递归可枚举）。另一方面，L_u 的补码（我们称它为 L_nu）甚至在 RE 中也没有，因为如果是，L_u 和 L_nu 都必须是递归的。
如果我们能够将 L_nu 简化为 L_ne，我们将证明 L_ne 也是非 RE。这意味着这种减少应该是不可能的。但是，我不知道为什么会这样。
首先，为了将语言 L 简化为 L'，我们必须构造一个可计算函数 f，它将 L 的每个可能的正实例映射到 L' 的某个正实例，并将 L 的每个可能的负实例映射到 L' 的某个负实例。仅此而已，不是吗？
其次，我认为我们可以有把握地假设通用图灵机 (UTM) 有两个最终状态，一个是状态和一个否状态。当然，如果 w \not\in L(M) 对于给定的输入 (M, w)，UTM 将永远不会到达 NO 状态，但我们仍然可以假设如果 UTM 停止，它将在 YES 状态或 NO 状态下这样做。这也是正确的，不是吗？
现在让我们尝试将 L_nu 简化为 L_ne，如下所示：给定一对 (M, w)，构建一个机器 M'，使用 UTM 的逻辑在 w 上运行 M，如果 UTM 说是，则说否，反之亦然。显然，L_nu 的正实例（w \not\in L(M)）映射到 L_ne 的正实例（L(M') 在这种情况下是非空的，因为 M' 总是说是），而 L_nu 的负实例 ( w \in L(M)) 被转换为 L_ne 的负实例（L(M') 是空的，因为 M' 总是说 NO）。虽然机器 M' 显然对于至少一些正输入永远运行（因为至少有一对 (M, w) 与 w \not\in M 使得 UTM 永远运行），减少本身是可计算的：M' 的代码包括 UTM 的代码（这绝对可以完成）和一个简单的逻辑，用于检查内置 UTM（如果应用于 (M, w)）是否已到达 YES 状态或到 NO 状态。就是这样。
因此，我刚刚“证明”了 L_ne 是非 RE。但是，由于情况并非如此，我一定是在某个地方出错了。这真的让我感到困惑，因为从 L_u 到 L_ne 的标准简化，例如，Hopcroft-Ullman-Motwani 中给出的，采用了非常相似的推理。
如果有人能帮我解开这个谜语，我将不胜感激！