Question

能轻松定义的问题，计算机却无法解决，真令人沮丧。但是，这个特定的问题相当抽象，而且我们用来描绘它的 do_the_opposite.rb 程序也不实际而且做作。我们想要 #halts? 实际执行，或者作为一个现实世界应用的一部分写一个 do_the_opposite.rb 的程序看起来不太可能。或许我们可以无视不可判定性，将其作为一个学术“玩具”，然后继续我们的生活。

遗憾的是，没那么简单，因为停机问题不是唯一的不可判定问题。我们日常构建软件的过程中可能想要解决大量问题，而它们的不可判定性对于自动化工具和过程的实际限制非常重要。

来看个小例子。假设我们已经接受了一个任务，要开发一个输出'hello world' 的 Ruby 程序。听起来相当简单，但按照长期以来的固有模式，我们 16 还要开发一个自动化工具，它能可靠地判定是否存在一个特定的程序在提供一个特定的输入时能输出 hello world。17 有了这个工具，我们可以分析最终的程序，然后检查它是否做了应该做的事情。

16当然是“负责任的软件工程专业人员”。

17如果程序没有实际从 $stdin 读取任何东西，输入可能是无关的，但为了完整性和一致性我们会把它包含进来。

现在，假设我们成功开发了一个方法 #prints_hello_world?，它能正确地对所有程序做出判断。忽略掉实现细节，方法会是这种普遍的形式：

def prints_hello_world?(program, input)
  # 解析程序
  # 分析程序
  # 如果程序打印 "hello world"，就返回 true，否则返回 false
end

写完最初的程序之后，我们可以使用#prints_hello_world? 来验证它做了正确的事情；如果做得对，就把它签入到源代码里，发邮件给老板，然后所有人都会很高兴。但情况甚至更好，因为还能使用 #prints_hello_world? 实现另一个有趣的方法：

def halts?(program, input)
  hello_world_program = %Q{
    program = #{program.inspect}
    input = $stdin.read
    evaluate(program, input) # evaluate program, ignoring its output
    print 'hello world'
  }

  prints_hello_world?(hello_world_program, input)
end

%Q 语法引用字符串的方式与 %q 一样，之后会执行替换，因此 #{program.inspect} 会被一个包含 program 值的 Ruby 字符串替换掉。

我们新版本的 #halts? 通过构建一个特殊的程序 hello_world_program 来工作，它主要干两件事情：

1.用标准输入中的input 为参数对 program 求值；
2. 输出 hello world。

hello_world_program 此时执行只有两种可能的结果：要么 evaluate(program, input) 成功结束，在这种情况下hello world 将会被输出，要么 evaluate(program, input) 将会永远循环，也就根本没有输出。

把这个程序提供给#prints_hello_world?，以查明那两个结果中哪个将会发生。如果#prints_hello_world? 返回 true，那意味着 evaluate(program, input) 最终将结束，并允许hello world 输出，因此#halts? 返回 true 以标识这个程序对于 input 会停机。相反，如果#prints_hello_world? 返回false，那一定是因为hello_world_program 永远也无法到达它的最后一行，因此 #halts 返回 false，以此来说明 evaluate(program, input)会永远循环。

我们对#halts? 的新实现表明停机问题可以规约成检查一个程序是否会输出hello world的问题。换句话说，任何计算 #prints_hello_world? 的算法都能改成计算 #halts? 的算法。

我们已经知道一个可工作的 #halts? 不可能存在，因此明显的结论是 #prints_hello_world?的完整实现也不可能存在。如果不可能实现，邱奇－图灵论题表明不存在这样的算法，因此“这个程序是否会输出 hello world ？”是另一个不可判定的问题。

在现实中，没有人关心自动检查一个程序是否会输出特定的字符串，但这个不可判定性证明的结构指向了某种更大更普遍的情况。我们需要构建一个程序，只要其他某个程序停机了，它就展示“print hello world”属性（输出 hello world），这对展示不可判定性足够了。

无法重用这种方法的所有程序行为的属性中，有我们确实关心的属性吗？ 没有。这是 Rice 定理：程序行为的任何非平凡性质都是不可判定的，因为停机问题总是能被规约成判定这个属性是否为 true 的问题；如果我们能发明一个算法来判定那个属性，就能使用它来构建另一个算法来判定停机问题，而这是不可能的。

概括地讲，一个“非平凡的属性”是对程序做什么而不是程序怎么做的一个要求。例如，Rice 定理对于像“这个程序的源代码包含字符串'reverse'吗？”这样的问题并不适用，因为这是一个实现细节，能在不改变程序外部可视行为的前提下重构掉。换句话说，像“这个程序是输出它输入的逆向吗？”这样的语义性质是在 Rice 定理范围内的，从而是不可判定的。

Rice 定理告诉我们存在大量关于一个程序执行时会干什么的不可判定的问题。