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

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

Difficult TaskEasy TaskSolveReducingRelatively easyStraightforward and hard

我们回归主题上来,现在我们想证明 L_u 的不可判定性。 L_u 的一般数学形式为:给定一个语言 L_u 满足: % <![CDATA[ L_u = \{ <M, w> \mid w \in L(M) \} %]]> 。即给定一个图灵机的编码和一段字符串,判定这段字符串是否可以被图灵机接受。

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

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

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

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

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



发现存在错别字或者事实错误?请麻烦您点击 这里 汇报。谢谢您!