21.1.1. 引言¶

即使是好程序员，有时也会写出进入无限循环的程序。 当然，当你运行一个尚未停止的程序时，你并不确切知道 它只是一个很慢的程序，还是一个处于无限循环中的程序。 在"足够长的时间"之后，你会关掉它（或者它因为其他原因停止工作）。 如果你的编译器能在运行前检查你的程序并告诉你它会进入 无限循环，那该多好？ 更具体地说，给定一个程序和一个特定输入，如果能不实际运行 程序就判断出在该输入上执行它是否会陷入无限循环， 那将很有用。

不幸的是，停机问题 （它就是 这么命名的）是无法解决的。 永远不会存在一个计算机程序，能够针对任意程序 \(P\)， 确定性地判断 \(P\) 是否对所有输入停机。 甚至也永远不会存在一个计算机程序，能够确定性地判断 任意程序 \(P\) 是否对指定输入 \(I\) 停机。 怎么会这样？ 程序员经常检查程序以判断它们是否会停机。 这理应可以自动化。 作为对那些认为任何程序都能以此方式分析的人的警告， 在读下去之前，请仔细检查下面的代码片段。

while (n > 1)
  if (ODD(n))
    n = 3 * n + 1;
   else
     n = n / 2;

while (n > 1)
  if (ODD(n))
    n = 3 * n + 1;
   else
     n = n / 2;

这是一段著名的代码。 这段代码赋给 \(n\) 的值序列有时被称为 输入值 \(n\) 的 考拉兹序列。 这段代码片段对所有 \(n\) 值都会停机吗？ 没有人知道答案。 所有尝试过的输入都会停机。 但它总是停机吗？ 注意，对于这段代码片段，因为我们不知道它是否停机， 我们也不知道它运行时间的上界。 至于下界，我们容易证明 \(\Omega(\log n)\)。

就个人而言，我相信某一天某个聪明人会 完整地分析考拉兹函数，一劳永逸地证明 这段代码片段对所有 \(n\) 值都会停机。 这样做很可能能给我们带来提升整体算法分析能力的技术。 不幸的是，来自 可计算性—计算机科学中 研究用计算机不能做什么的分支—的证明 迫使我们相信，总会有另一段 我们无法分析的程序代码。 这正是停机问题不可解这一事实的结果。

21.1.2. 不可数性¶

在证明停机问题不可解之前，我们先证明 并非所有函数都能实现为计算机程序。 之所以必然如此，是因为程序的个数远远少于 可能函数的个数。

如果一个集合的每个成员都能被唯一地指派给一个正整数， 那么该集合是 可数 的（如果它是一个成员 无限的集合，则称 可数无限）。 如果不能把集合的每个成员都指派给它自己的正整数，那么 该集合是 不可数 的 （或称 不可数无限）。

要理解"被指派给一个正整数"是什么意思， 设想有一排无限多个箱子，分别标号为 1、2、3，依此类推。 取一个集合，开始把集合的成员放入箱子，每个箱子至多放一个成员。 如果我们能找到一种方式把集合的每个成员都指派给它自己的箱子， 那么这个集合就是可数的。 例如，考虑正偶数整数 2、4 等等的集合。 我们可以把正偶数 \(i\) 指派给箱子 \(i/2\) （或者，如果我们不介意漏掉一些箱子，可以把偶数 \(i\) 指派给箱子 \(i\)）。 因此，偶数整数集合是可数的。 这不足为奇，因为直觉上正偶数整数的数量"少于" 正整数，尽管两者都是无限集合。 但实际上正整数并不比正偶数整数更多， 因为我们可以把每个正整数唯一地指派给某个正偶数， 只须把正整数 \(i\) 指派给正偶数 \(2i\)。

另一方面，所有整数的集合也是可数的，尽管这个集合 看起来比正整数集合更大。 这是因为我们可以把 0 指派给正整数 1，把 1 指派给正整数 2， 把 -1 指派给正整数 3，把 2 指派给正整数 4， 把 -2 指派给正整数 5，依此类推。 一般来说，把正整数 \(i\) 指派给正整数 \(2i\)， 把负整数 \(-i\) 指派给正整数 \(2i+1\)。 我们永远不会用完可用的正整数（箱子）， 并且我们确切知道每个整数被指派给了哪个正整数（箱子）。 因为每个整数都得到了指派，所以整数集合是 可数无限的。

程序的个数是可数还是不可数的？ 程序可以看作只是字符串（包括特殊标点字符、空格和换行）。 让我们假设程序中可以出现的不同字符个数为 \(P\)。 （使用 ASCII 字符集，\(P\) 必须小于 128， 但实际数值无关紧要）。 如果字符串的个数是可数的，那么程序数量 当然也是可数的。 我们可以如下把字符串指派给箱子。 把空字符串指派给第一个箱子。 现在，取所有单字符字符串，把它们按"字母"序或 ASCII 码序 指派给接下来的 \(P\) 个箱子。 接着，取所有双字符字符串，把它们按从左到右的 ASCII 码次序 指派给接下来的 \(P^2\) 个箱子。 三字符字符串同样被指派给箱子，然后 是长度为四的字符串，依此类推。 这样，任何给定长度的字符串都能被指派给 某一个箱子。

通过这一过程，任何有限长度的字符串都被指派给 某个箱子。 所以任何程序（它不过是一个有限长度的字符串）都被 指派给了某个箱子。 因为所有程序都被指派给了某个箱子，所以所有程序的集合 是可数的。 自然，箱子中的大多数字符串并不是合法程序，但 这无关紧要。 重要的是，那些 确实 对应程序的字符串也在 箱子中。

现在我们来考虑可能函数的数量。 为简单起见，假设所有函数都以单个正整数为输入、 并以单个正整数为输出。 我们即将看到，光是这类函数就已经绰绰有余。 我们把这样的函数称为 整数函数。 函数不过是从输入值到输出值的映射。 当然，并非所有计算机程序都严格以整数为输入、 以整数为输出。 然而，计算机读写的一切 本质上都是一系列的数字，可能被解释为字母 或其他内容。 任何有用的计算机程序的输入和输出都可以编码为整数值， 所以我们这种简单的计算机输入输出模型 足以涵盖所有可能的计算机程序。

现在我们希望看看是否可能把所有的整数 函数指派给无限集的箱子。 如果是这样，那么函数的个数是可数的，从而 有可能把每个整数函数都指派给一个程序。 如果整数函数的集合无法指派给箱子，那么 将会有一些整数函数必然没有对应的程序。

把每个整数函数想象成一张两列无限行 的表。 第一列列出从 1 开始的所有正整数。 第二列列出当输入第一列的值时函数的输出。 于是，这张表明确描述了每个函数从输入到输出的映射。 把它称为函数表。

接下来我们要尝试把函数表指派给箱子。 为此我们必须给函数排序，但我们选择什么顺序 无关紧要。 例如，箱子 1 可以存放无论输入值如何总是返回 1 的函数。 箱子 2 可以存放返回其输入的函数。 箱子 3 可以存放把输入翻倍再加 5 的函数。 箱子 4 可以存放一个我们看不到其输入输出简单关系 的函数。 [1] 这四个被指派到前四个箱子的函数如图 25.21.1 所示。

我们能把每个函数都指派给一个箱子吗？ 答案是不能，因为总有一种方法能创建出不在任何箱子中的 新函数。 假设某人提出一种把函数指派给箱子的方法， 并声称它包含了所有函数。 我们可以构建一个尚未被指派给任何箱子的新函数，如下。 从第一个箱子中取输入 1 的输出值。 把这个值称为 \(F_1(1)\)。 给它加 1，把这个结果指派为输入值 1 处这个新函数的输出。 无论我们给新函数指派的其他值是什么，它必定 不同于表中的第一个函数，因为 两者在输入 1 处给出的输出不同。 现在取表中第二个函数在 2 处的输出值 （称为 \(F_2(2)\)）。 给这个值加 1，把它指派为新函数在 2 处的输出。 因此，我们的新函数必定不同于箱子 2 的函数， 因为它们在第二个值处至少会有差别。 继续以这种方式进行，对所有值 \(i\) 指派 \(F_{new}(i) = F_i(i) + 1\)。 于是，新函数至少在位置 \(i\) 处不同于任何函数 \(F_i\)。 这种构造一个不在表中函数的过程被称为 对角线化。 因为新函数不同于每一个其他函数，所以它必定 不在表中。 无论我们如何尝试把函数指派给箱子，这都是成立的， 所以整数函数的个数是不可数的。 其意义在于：并非所有函数都能被 指派给程序，所以 必然 存在没有对应程序的函数。 图 25.21.2 说明了这一论证。

21.1.3. 停机问题不可解¶

知道存在 某些 计算机程序无法计算的函数， 也许具有智识上的吸引力。 但是没有程序能计算一个如图 25.21.1 中 箱子 4 那样的"无意义"函数，真的要紧吗？ 单凭这一点不一定意味着存在 有用的 函数无法计算。 毕竟，宇宙不应该这么别扭，对吧？ 也许正是我们能轻松为想要计算的函数提供精确定义 这一事实，意味着必定存在计算它的算法。

不幸的是，并非如此。 现在我们来证明任何计算机程序都无法计算停机问题。 证明用反证法。

我们从假设存在一个名为 halt 的函数能 解决停机问题开始。 显然，不可能写出一个不存在的东西，但这里给出一个 如果『解决停机问题的函数』真的存在、它大概是什么样子的 合理清单。 函数 halt 接受两个输入：一个表示程序或函数 源代码的字符串，以及另一个表示输入的字符串，用来判断输入程序 或函数是否会在此输入上停机。 函数 halt 做一些工作以做决定（这部分被封装进 一个假想函数 PROGRAM_HALTS）。 然后，如果输入程序或函数确实在给定输入上停机，函数 halt 返回 TRUE，否则返回 FALSE。

bool halt(String prog, String input) {
  if (PROGRAM_HALTS(prog, input))
    return true;
  else
    return false;
}

现在我们考察两个显然可以存在的简单函数， 因为这里给出了它们的完整代码。

// Return true if "prog" halts when given itself as input
bool selfhalt(String prog) {
  if (halt(prog, prog))
    return true;
  else
    return false;
}

// Return the reverse of what selfhalt returns on "prog"
void contrary(String prog) {
  if (selfhalt(prog))
    while (true); // Go into an infinite loop
}

如果我们写一个程序，其唯一目的是执行 函数 contrary，并以该程序自身作为输入来运行， 会发生什么？ 一种可能是对 selfhalt 的调用返回 TRUE； 也就是说，selfhalt 声称 contrary 在自身上运行时会停机。 在这种情况下，contrary 进入无限循环 （因而不会停机）。 另一方面，如果 selfhalt 返回 FALSE，那么 halt 是在宣称 contrary 不会在自身上停机， 于是 contrary 返回，也就是说它会停机。 因此，contrary 所做的恰好与 halt 所说的相反。

contrary 的行为与 "halt 正确解决停机问题"这一假设在逻辑上不一致。 我们并没有做出其他可能导致这种不一致的假设。 因此，通过反证，我们证明了 halt 无法 正确解决停机问题，从而不存在能 解决停机问题的程序。

现在我们已经证明了停机问题不可解，我们可以 用归约论证来证明其他问题也不可解。 策略是：假设存在一个求解该问题的计算机程序， 并用这个程序去求解另一个已知不可解的问题。

有许多我们希望计算机做的事情都是不可解的。 其中很多与程序的行为有关。 例如，证明任意程序是"正确的"，也就是证明某个程序 计算某个特定函数，就是一种关于程序行为的证明。 因此，能做到的极为有限。 其他一些不可解问题包括：

• 程序是否在每个输入上都停机？

• 程序是否计算某个特定函数？

• 两个程序是否计算同一个函数？

• 程序中的某一行是否被执行？

这并 不 意味着无法编写出能处理特殊情形（甚至可能处理 我们想要检查的大多数程序）的计算机程序。 例如，有些 C 编译器会检查 while 循环的控制表达式 是否是求值为 FALSE 的常量表达式。 如果是，编译器会发出警告，说该 while 循环代码永远不会执行。 程序员觉得这个特例足够有用，值得把它 加进编译器。 但是，不可能编写一个计算机程序，对 所有 输入程序检查 当程序被给定某个指定输入时某行指定代码是否会被执行。

另一个不可解的问题是程序是否含有计算机病毒。 "含有计算机病毒"这一属性是一个行为问题。 因此，不可能确定性地判断任意程序是否含有计算机病毒。 幸运的是，有许多好的启发式方法可以判断某个程序 是否可能含有病毒，而且通常能够 判断一个程序是否含有特定病毒，至少对现在已知的病毒而言是如此。 真正的病毒检测器工作得相当好， 但是，恶意的人总有可能发明出现有病毒检测器 无法识别的新病毒。