“证明 $$L_d$$ 的不可判定性”

问题是一个非常基本的不可判定问题，我们可以非常方便得将 问题规约到其他问题来证明其他问题的不可判定性。

的一般数学表达为：给定一个语言 满足：

判断 是否可决定 (decidable)。 和 分别指第 个字符串和第 个图灵机。换一句话说，判定一个图灵机是否可以停机接受它自己的编码。

为了证明 的不可判定性，我们这样思考：

我们假设 是可判定的，由于 一定是一个定义在 上的语言，所以 一定是也是某一个图灵机的语言。我们假设这一个图灵机是第 个图灵机，即 。我们同时假设第 个字符串为 ，这时，我们考虑，这个 在 中吗？

如果 ，则 。根据 的定义，，所以 。

如果 ，则 。这时根据 的定义， 。

综上所诉，不管 在不在 里面，这里都会出现矛盾。我们只能考虑我们的前提错了，即 不可判定。