“$$L_u$$ 问题不可判定性的证明”

现在我们已经知道了 问题是不可判定的了，那么我们应该如何使用类似 这样的我们已经知道是不可判定了的问题呢？答案是：我们通过他们来证明更多问题的不可判定性。在这个过程中我们要使用一种叫做归约 (Reduce) 的方法。

规约简单的说，就是一个偷懒的过程，一个化简问题的过程。例如你已经知道了如何计算一个圆的面积，那如何来计算两个圆的面积呢？答案是将「计算两个圆的面积」这个我们未知的、高难度的问题化简到「做两次计算一个圆的面积」这样的我们已知的、简单的问题。这个过程就叫做归约。生活中人们经常使用归约来解决问题，当人们要去做一些有挑战性的任务时，往往第一步是思考能不能把这个问题转换成一个已经解决了的问题，这就是在无意中使用了归约的思想。

我们回归主题上来，现在我们想证明 的不可判定性。 的一般数学形式为：给定一个语言 满足： 。即给定一个图灵机的编码和一段字符串，判定这段字符串是否可以被图灵机接受。

当我们使用归约的思想来用一个已知的不可判定问题 判定另一个问题 的不可判定性时，一般步骤如下：

1. 假设 可已被判定，即存在一个算法 来解决 问题。
2. 设法使用 解决 问题。
3. 因为 已知不可判定，即没有算法可以解决它，所以 不存在，所以 不可判定。

所以我们首先假设 问题可判定，即存在一个判别器 可以判断 。若 存在，则我们可以按如下的步骤来判断 问题：

1. 对于 ，我们有一个 。首先我们检测 是否是一个图灵机。检测字符串是否为图灵机是可以被做到的，因为图灵机的编码化遵守一系列的规则，我们只需要一个规则一个规则地去检测是否合理。
2. 若 不是一个图灵机，则我们可以理解为由 构成的不存在的图灵机的语言 。即 不在 所构成的不存在的图灵机的语言中。那么我们根据 的定义，接受 并停机。
3. 若 是一个图灵机，那么我们把 传给 的判别器 。因为我们假定 存在，所以不管 构成的图灵机接不接受字符串 ，都会停机。
4. 若判别器 告诉我们 ，则根据 定义，。若 ，则 。

于是，我们成功用 的判别器 判断了 ，但我们知道 是不可判定的，所以只有可能我们整个证明的前提发生了错误。即 不可判定。