Question

大量的非判定性问题是关于机器和程序执行过程中的行为的。这其中最著名的就是停机问题，停机问题要解决的是对拥有一条特定纸带的特定图灵机判定它的执行是否能够停机。感谢通用性，我们可以把同样的问题用更实际的名词重讲一遍：给定一个包含 Ruby 程序源代码的字符串，还有一个数据的字符串可以让程序从标准输入中读取，那么运行这个程序最终会得到一个答案作为结果还是只会无限循环下去呢？

8.3.1　构建停机检查器

停机问题应该被看成是不可判定的，尽管原因并不明显。对于一个可回答的问题写出程序是比较容易的。下面是一个不管它的输入字符串是什么，都能确定停机的程序：

input = $stdin.read
puts input.upcase

我们假设$stdin.read 总是会立即返回一个值——换句话说，每个程序的标准输入是有限的和不会阻塞的——因为我们关注的是程序的内部行为，而不是它与操作系统的交互。

反过来说，对源代码做小小的改动就可以产生一个明显永远不停机的程序：

input = $stdin.read

while true
  # 什么也不做
end

puts input.upcase

我们当然可以写出一个停机检查器来区分这两种情况。只是测试程序的源代码是否含有字符串 while true 就够了：

def halts?(program, input)
  if program.include?('while true')
    false
  else
    true
  end
end

这个#halts?方法的实现在下面两个示例程序中会给出正确的答案：

>> always = "input = $stdin.read\nputs input.upcase"
=> "input = $stdin.read\nputs input.upcase"
>> halts?(always, 'hello world')
=> true
>> never = "input = $stdin.read\nwhile true\n# do nothing\nend\nputs input.upcase"
=> "input = $stdin.read\nwhile true\n# do nothing\nend\nputs input.upcase"
>> halts?(never, 'hello world')
=> false

但#halts? 对其他程序很可能是错的。例如，存在这样的程序，它们的停机行为依赖于它们的输入值：

input = $stdin.read

if input.include?('goodbye')
  while true
    # 什么也不做
  end
else
  puts input.upcase
end

因为知道搜索什么，所以我们可以总是扩展停机检查器来处理这样的特殊情况：

def halts?(program, input)
  if program.include?('while true')
    if program.include?('input.include?(\'goodbye\')')
      if input.include?('goodbye')
        false
      else
        true
      end
    else
      false
    end
  else
    true
  end
end

现在我们有了一个检查器，它能对三个程序和任意可能的输入字符串给出正确的答案：

>> halts?(always, 'hello world')
=> true
>> halts?(never, 'hello world')
=> false
>> sometimes = "input = $stdin.read\nif input.include?('goodbye')\nwhile true\n
# 执行 nothing\nend\nelse\nputs input.upcase\nend"
=> "input = $stdin.read\nif input.include?('goodbye')\nwhile true\n# do nothing\n
end\nelse\nputs input.upcase\nend"
>> halts?(sometimes, 'hello world')
=> true
>> halts?(sometimes, 'goodbye world')
=> false

我们可以像这样无限继续下去，增加更多的检查和更多的特殊情况，以支持对实例程序的所有扩展，但我们永远都无法得到判定任意程序是否会停机的全部问题的答案。一个暴力的实现可能会越来越准确，但总是会有盲点；简单的查找特殊语法模式的方法不可能满足所有的程序。

让#halts?能在通常情况下对任何可能的程序和输入都工作看起来有些困难。如果一个程序含有任何循环——不管是显式的，如 while 循环，或者隐式的，如递归方法调用——那它都有可能一直运行下去，预测对于给定输入的任何东西都需要对程序含义的熟练分析。

作为人类，我们可以立即看出来下面这个程序总是能停机：

input = $stdin.read
output = ''

n = input.length
until n.zero?
  output = output + '*'
  n = n - 1
end

puts output

但是为什么它总是能停机呢？当然不是因为任何直接的语法原因。解释是 IO#read 总会返回一个String，而 String#length 总会返回一个非负的 Integer，并且不断对非负的Integer 调用 -（1）最终总是会产生一个对象，它的 #zero? 方法会返回 true。这个推理链很微妙而且对于小的修改会高度敏感；如果循环中的语句 n=n-1 变成 n=n-2，程序将只会在偶数长度个输入时才会停机。停机检查器需要知道所有这些关于 Ruby 和数的事实，还要知道如何把事实连到一起以便对这种程序的判定能准确。这样的检查器需要大而复杂。

最基本的困难是不实际执行一个程序很难预测它将会干什么。运行程序#evaluate 看它是否会停机是很诱人的，但那样做没有好处：如果程序不停机，#evaluate 将会永远运行下去，而不管我们等多久，都不会从 #halts?获得任何应答。任何可以依赖的停机检测算法都需要在有限的时间内通过检查和分析程序的文本来生成确定的答案，而不是单纯依靠运行程序和等待。

8.3.2　永远不会有结果

好吧，直觉告诉我们 #halts? 很难正确实现，但那并不意味着停机问题是不可判定的。有大量的难题（例如写出 #evaluate）被证明只要付出足够的努力和创造力，都是能解决的。如果停机问题是不可判定的，那就意味着 #halts? 不止是极端困难，而是不可能写出来。

如何才能知道 #halts? 的恰当实现不可能存在呢？如果它仅仅是一个工程问题，为什么我们不能投入大量的程序员，并最终获得一个解决方案呢？

1. 好得不真实

我们假设停机问题是可判定的。在这个假想的世界里，写一个 #halts? 的完整实现是可能的，因此对 #halts?(program,input) 的调用在任何 program 和 input 下，总是返回 true或者 false，并且如果以标准输入的input 运行，这个答案总是能正确地预测program 是否能停机。方法#halts? 的原始结构可能像下面这样：

def halts?(program, input)
  # 解析程序
  # 分析程序
  # 如果程序在输入上停机，就返回 true，否则返回 false
end

如果可以写#halts?，那么我们可以构建 does_it_halt.rb，这个程序能读取另一个程序（作为输入），并在读取到空字符串的时候根据那个程序是否停机来输出 yes 或者 no：12

12空字符串的选择并不重要；只是任意的一个固定输入。这个设计是在自包含的程序上运行 does_it_halt.rb，程序不从标准输入读取任何东西，因此输入是什么并不重要。

def halts?(program, input)
  # 解析程序
  # 分析程序
  # 如果程序在输入上停机，就返回 true，否则返回 false
end

def halts_on_empty?(program)
  halts?(program, '')
end

program = $stdin.read

if halts_on_empty?(program)
  print 'yes'
else
  print 'no'
end

有了 does_it_halt.rb 之后，就可以使用它解决非常难的问题。考虑一下 1742 年克里斯蒂安·哥德巴赫提出的著名论断：

任何一个大于 2 的整数都可以写成两个质数之和。

这就是哥德巴赫猜想，因为还没有人能证明它是真还是假，所以它很著名。有证据表明它是真的，因为任选的一个偶数总是可以分成两个质数——12 = 5 + 7、34 = 3 + 31、567 890 = 7 + 567 883，等等—已经检查过它对 4 和 4 000 000 000 000 000 000 之间的所有偶数都成立。但存在无限多个偶数，因此没有计算机能把它们都检查出来，对每个偶数一定可以用这种方式拆分也没有已知的证明。尽管可能性小，但仍有可能存在某个非常大的偶数不是两个质数的和。

证明哥德巴赫猜想是数论的圣杯之一。2000 年，英国费伯出版社悬赏 100 万美元给能证明哥德巴赫猜想的人。但等一下：我们已经有了能发现这个猜想是真的工具了啊！只需要写一个程序，搜索反例即可：

require 'prime'

def primes_less_than(n)
  Prime.each(n - 1).entries
end

def sum_of_two_primes?(n)
  primes = primes_less_than(n)
  primes.any? { |a| primes.any? { |b| a + b == n } }
end

n = 4

while sum_of_two_primes?(n)
  n = n + 2
end

print n

这在哥德巴赫猜想的真实性和一个程序的停机行为之间建立了联系。如果猜想是真的，这个程序将永远无法找到反例，不管它计数到多少，因此它将会永远循环下去；如果猜想是假的，n 将最终被赋予一个偶数值，这个偶数值不是两个质数的和，并且程序将会停机。因此我们只需要把它保存成 goldbach.rb 并运行 ruby does_it_halt.rb < goldbach.rb，以查明 这是否是一个停机程序，而那将告诉我们哥德巴赫猜想是否是真的。100 万美元是我们的了！ 13

13费伯出版社的奖金在2002年过期了，但今天任何能给出证明的人仍然将在明星数学家圈子中名利双收。

好了，很明显这好得都不真实了。写出能准确预测 goldbach.rb 行为的程序将会要求精通超越我们当前理解的数论知识。数学家已经工作了几百年试图证明或者证伪哥德巴赫猜想；一群贪得无厌的软件工程师构建出一个 Ruby 程序，奇迹般地不止解决这个问题，还能解决可以表达成循环程序的任何未解数学猜想是不可能的。

2. 根本就不可能

到目前为止我们已经看到了很强的证据表明停机问题是不可判定的，但还没有看到确定性的证明。我们的直觉可能是只通过把哥德巴赫猜想转成一个程序就证明或者推翻它是不可能的，但计算有时候是非常违背直觉的，因此我们不应该被多么不可能的东西说服。如果停机问题确实是不可判定的，而不是简单的难以判定，我们应该能够证明它。

下面是为什么 #halts? 永远不能工作。如果它工作，我们就能构建一个新的方法 #halts_on_itself?，这个方法调用 #halts? 以决定一个程序在把它自己的源代码作为输入运行时会做什么：14

14这是对 8.1.4 节中#evaluate_on_itself 的重现，只是用 #halts? 替换了 #evaluate。

def halts_on_itself?(program)
  halts?(program, program)
end

就像 #halts? 一样，#halts_on_itself? 方法总会结束并返回一个布尔值：如果program 以自己作为输入时能停机就是true，如果永远循环就是false。

给定#halts? 和 #halts_on_itself? 的实现，我们可以写一个叫作do_the_opposite.rb 的程序：

def halts?(program, input)
  # 解析程序
  # 分析程序
  # 如果程序在输入上停机，就返回 true，否则返回 false
end

def halts_on_itself?(program)
  halts?(program, program)
end

program = $stdin.read

if halts_on_itself?(program)
  while true
    # 什么也不做
  end
end

这段代码从标准输入中读取 program，查明如果自身为输入时它是否会停机，并立即做相反的动作：如果 program 能停机，do_the_opposite.rb 永远会循环；如果 program 永远循环，do_the_opposite.rb 会停机。

现 在，ruby do_the_opposite.rb < do_the_opposite.rb 会 做 些什么呢？ 15 就 像我们之前用 does_it_say_no.rb 看到的那样，这个问题创造了不可避免的矛盾。

15或者等价地说：如果我们用 do_the_opposite.rb 的源代码作为它的参数调用它，#halts_on_itself?会返回什么呢？

在给定 do_the_opposite.rb 的源码作为参数时，方法 #halts_on_itself? 要么返回true 要么返回 false。如果它用返回true表示停机程序，那么ruby do_the_opposite.rb < do_the_opposite.rb 将会永远循环下去，这意味着#halts_on_itself是错误的。另一方面，如果#halts_on_itself? 返回 false，make do_the_opposite.rb 会立刻停机，又一次与#halts_on_itself? 的预测矛盾。

这里错在选择 #halts_on_itself?——它只是一个无辜的小程序，作为 #halts 的代码并依赖它的答案。我们真正展示的是在用do_the_opposite.rb 既作为 program 又作为 input 的参数时，#halts? 不能返回一个满意的答案；不管如何努力工作，它产生的任何结果都是错的。那意味着对于 #halts?，任何真正的实现只存在两种可能的命运：

· 给出错误的答案，如即使 do_the_opposite.rb 能停机也预测它永远循环下去（反过来也是这样）；

· 永远循环而且从来也不会返回任何答案，就像ruby does_it_say_no.rb < does_it_say_no.rb里#evaluate 做的那样。

因此一个 #halts? 完全正确的实现永远不会存在：对于输入，它要么做出错误的预测，要么根本就做不出预测。

回忆一下可判定性的定义：

一个判定问题如果存在一个算法能保证对于任何可能的输入都能在有限时间内解决，这个问题就是可判定的。

我们应该证明了写一个 Ruby 程序完全解决停机问题是不可能的，而且既然 Ruby 程序与图灵机等价，所以图灵机也是不可能的。邱奇－图灵论题说的是所有的算法都能由一台图灵机执行，因此如果不存在能解决停机问题的图灵机，也不会存在算法；换句话说，停机问题是不可判定的。