如何通俗地解释停机问题？

Posted on

这篇文章转载自我在知乎上的回答

我用 Python 伪代码来解释下，我觉得对这个问题有兴趣的应该都是有点编程基础的，所以直接上 code 应该是最容易的。

背景知识

「停机问题」研究的是：是否存在一个「程序」，能够判断另外一个「程序」在特定的「输入」下，是会给出结果（停机），还是会无限执行下去（不停机）。

在下文中，我们用「函数」来表示「程序」，「函数返回」即表示给出了结果。

正文

我们假设存在这么一个「停机程序」，不管它是怎么实现的，但是它能够回答「停机问题」：它接受一个「程序」和一个「输入」，然后判断这个「程序」在这个「输入」下是否能给出结果：

1
2
3
def is_halt(program, input) -> bool:
  # 返回 True  如果 program(input) 会返回
  # 返回 False 如果 program(input) 不返回

（在这里，我们通过把一个函数作为另一个函数的输入来描述一个「程序」作为另一个「程序」的「输入」，如果你不熟悉「头等函数」的概念，你可以把所有文中的函数对应为一个具备该函数的对象。）

为了帮助大家理解这个「停机程序」的功能，我们举个使用它的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from halt import is_halt

def loop():
  while(True):
      pass

# 如果输入是 0，返回，否则无限循环
def foo(input):
  if input == 0:
    return
  else:
    loop()

is_halt(foo, 0)  # 返回 True
is_halt(foo, 1)  # 返回 False

是不是很棒？

不过，如果这个「停机程序」真的存在，那么我就可以写出这么一个「hack 程序」：

1
2
3
4
5
6
7
8
9
10
11
from halt import is_halt

def loop():
  while(True):
      pass

def hack(program):
  if is_halt(program, program):
    loop()
  else:
    return

这个程序说，如果你 is_halt 对 program(program) 判停了，我就无限循环；如果你判它不停，我就立刻返回。

那么，如果我们把「hack 程序」同时当做「程序」和「输入」喂给「停机程序」，会怎么样呢？

1
is_halt(hack, hack)

你会发现，如果「停机程序」认为 hack(hack) 会给出结果，即 is_halt(hack, hack)) 返回 True) ，那么实际上 hack(hack) 会进入无限循环。而如果「停机程序」认为 hack(hack) 不会给出结果，即 is_halt(hack, hack) 返回 ，那么实际上 hack(hack) 会立刻返回结果……

这里就出现了矛盾和悖论，所以我们只能认为，我们最开始的假设是错的：

这个「停机程序」是不存在的。

意义

简单的说，「停机问题」说明了现代计算机并不是无所不能的。

上面的例子看上去是刻意使用「自我指涉」来进行反证的，但这只是为了证明方便。实际上，现实中与「停机问题」一样是现代计算机「不可解」的问题还有很多，比如所有「判断一个程序是否会在某输入下怎么样？」的算法、Hilbert 第十问题等等，wikipedia 甚至有一个 List of undecidable problems。

漫谈

如果你觉得只是看懂了这个反证法没什么意思：

  1. 最初图灵提出「停机问题」只是针对「图灵机」本身的，但是其意义可以被推广到所有「算法」、「程序」、「现代计算机」甚至是「量子计算机」。
  2. 实际上「图灵机」只能接受（纸带上的）字符串，所以在图灵机编程中，无论是「输入」还是另一个「图灵机」，都是通过编码来表示的。
  3. 「图灵机的计算能力和现代计算机是等价的」，更严谨一些，由于图灵机作为一个假象的计算模型，其储存空间是无限大的，而真实计算机则有硬件限制，所以我们只能说「不存在比图灵机计算能力更强的真实计算机」。
  4. 这里的「计算能力」（power）指的是「能够计算怎样的问题」（capablity）而非「计算效率」（efficiency），比如我们说「上下文无关文法」比「正则表达式」的「计算能力」强因为它能解决更多的计算问题。
  5. 「图灵机」作为一种计算模型形式化了「什么是算法」这个问题（邱奇－图灵论题）。但图灵机并不是唯一的计算模型，其他计算模型包括「Lambda 算子」、μ-递归函数」等，它们在计算能力上都是与「图灵机」等价的。因此，我们可以用「图灵机」来证明「可计算函数」的上界。也因此可以证明哪些计算问题是超出上界的（即不可解的）。
  6. 需要知道的是，只有「可计算的」才叫做「算法」。
  7. 「停机问题」响应了「哥德尔的不完备性定理」。

拓展阅读：

中文：

英文：