computer-science - 可判定性和递归可枚举性

Question

假设存在图灵机 M1、M2、M3，它们识别的语言分别是 L(M1)、L(M2) 和 L(M3)。以下语言
L = {(M1, M2, M3) : L(M1), L(M2), and L(M3) 不相等}
语言是可判定的吗？递归可枚举？或者两者都没有？

Answer 1

让MMi，我是一台模拟在输入I上运行其他机器Mi的机器并返回 true如果 Mi 最终停止在 I , 否则永远循环。

让 M∞ 是一个简单的永远循环的机器。

然后，(MMi,I, M∞, M∞) 是在 L 中，如果 Mi 在输入 I 上停止.

这将停机问题的可判定性降低到 L 的可判定性，因此 L 是不可判定的。

==============

接下来，让我们证明 L 不是通过矛盾递归可枚举的。

假设L是递归可枚举的，那么存在一个图灵机M，如果Mi、Mj和Mk是三个各自语言不相等的图灵机，那么M最终会吐出三元组(Mi，Mj，Mk)。

现在让我们考虑对 M 的修改，称为 M'，它是通过取 M 并将值 (M, M', M') 添加到 L(M') 来定义的。
要问的重要问题是 (M, M', M') 是否在 L 中？好吧，如果 (M, M', M') 在 L 中，那么 L(M) 不能等于 L(M')(否则它不符合 L 中的定义)，所以 L(M)不得包含 (M, M', M') (因为这是我们所做的唯一修改)。相反，如果 (M, M', M') 不在 L 中，则 L(M) != L(M')(因为我们将那个肚皮添加到 L(M'))，因此它必须在 L 中(M)，因为语言不相等。

因此，我们得出了一个悖论，即 M 不存在，因此 L 不可递归枚举。