浅谈停机问题

jiezi

5 年前

如果要计算 90 和 21 的最大公约数，根据欧几里德的定理，等同于求 21 和 6 的最大公约数，进一步等同于求 6 和 3 的最大公约数，经过几步转化，最终我们得到了结果：3。

这样一系列“有限”的步骤的集合，我们称之为算法。假设我们把求最大公约数算法的名字就叫做 GCD，当我们说 GCD 作用于 90 和 21 可以停机的时候，转成大白话就是：GCD(90, 21)不会陷入死循环，并且返回值是 3。事实上，GCD 对于“任何合法”的输入总是能停机的。

那么可不可以进一步问：有没有这样一个算法，对于任意一个给定的程序和输入，可以判断出这个程序是否会停机^{[[1]](https://en.wikipedia.org/wiki…}？

假设我们有一个程序，就叫 will-stop?，它可以针对任意的程序 algorithm 和输入 input，返回是否可以停机，写成伪代码就是：

bool will-stop?(algorithm, input) {// return true or false}

接着我们来设计一个叫 evil 的程序，它接受一个程序 algorithm，在内部，它调用 will-stop? 并根据返回做一个相反的动作。写成伪代码也就是：

void evil(algorithm) {if (will-stop?(algorithm, algorithm)) {
    // 当返回 true，就进行一个不能停机的死循环
    while(true)
  } else {
    // 当返回 false，就立即执行一个停机动作
    return
  }
}

接下来我们尝试用来判断一下 evil(evil)这个函数调用是否会停机。也就是：will-stop?(evil, evil)输出的到底是什么？

为了方便表述，我们同时也用 evil₁和 evil₂指代上面的 evil，也就是说 evil、evil₁、evil₂ 这 3 者是等价的。

下面我们用 will-stop?(evil₁, evil₂)代替之前的 will-stop?(evil, evil)。

假设 evil₁(evil₂)能停机，也就是 will-stop?(evil₁, evil₂)返回的是 true，我们把 evil₂代入到 evil₁的函数体中，也就说 evil₁内部的 will-stop?(evil₂, evil₂)返回的是 false，也就是说它告诉我们 evil₂(evil₂)不会停机。

别忘了 evil₁(evil₂)和 evil₂(evil₂)代表的其实都是 evil(evil)，所以 will-stop? 的结果自相矛盾了，那么反过来呢？

假设 evil₁(evil₂)不能停机，则 evil₁内部的 will-stop?(evil₂, evil₂)返回 true，也就是说它告诉我们 evil₂(evil₂)停机了。

证明的部分我参考了 Daniel Friedman^{[[2]](https://www.douban.com/douban…}以及刘未鹏 ^{[[3]](http://mindhacks.cn/2006/10/1…} 的实现。同时，做了一些表述上的优化，并补充了一些背景知识，使它看起来不单是一个冷冰冰的数学问题，过程中我参考了《计算进化史》^{[[4]](https://www.douban.com/douban…}。

[1] Halting problem
[2]《The Little Schemer – 4th Edition》
[3] 康托尔、哥德尔、图灵——永恒的金色对角线(rev#2)
[4]《计算进化史：改变数学的命运》

浅谈停机问题

最大公约数

证明部分

写在后面

参考资料