可判定性和递归可枚举性

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 k ) _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 不是递归可枚举的。