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

Question

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

Answer 1

让 M _{M i，I}是一台机器，它模拟在输入上运行其他机器 M _i并在 M _i最终停止时I返回，否则永远循环。trueI

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

然后， (M _{M i ,I} , M _∞ , M _∞ ) 在 L 中，当且仅当M _i在输入时停止I。

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

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

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

假设 L 是递归可枚举的，所以存在图灵机 M 使得如果 M _i、 M _j和 M _k是三个各自语言不相等的图灵机，那么 M 最终会吐出三元组 (M _i , M _j , M _k )。

现在让我们考虑对 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 不是递归可枚举的。