从最大公约数讲起
如果要计算90和21的最大公约数，根据欧几里德的定理，等同于求21和6的最大公约数，进一步等同于求6和3的最大公约数，经过几步转化，最终我们得到了结果：3。
这样一系列“有限”的步骤的集合，我们称之为算法。假设我们把求最大公约数算法的名字就叫做GCD，当我们说GCD作用于90和21可以停机的时候，转成大白话就是：GCD(90, 21)不会陷入死循环，并且返回值是3。事实上，GCD对于“任何合法”的输入总是能停机的。
那么可不可以进一步问：有没有这样一个算法，对于任意一个给定的程序和输入，可以判断出这个程序是否会停机[1]？
停机问题的一种证明方式
假设我们有一个程序，就叫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
}
}
接下来我们尝试用will-stop?来判断一下evil(evil)这个函数调用是否会停机。也就是：will-stop?(evil, evil)输出的到底是什么？为了方便表述，我们同时也用evil1和evil2指代上面的evil，也就是说evil、evil1、evil2 这3者是等价的。
下面我们用will-stop?(evil1, evil2)代替之前的will-stop?(evil, evil)。
假设evil1(evil2)能停机，也就是will-stop?(evil1, evil2)返回的是true，我们把evil2代入到evil1的函数体中，也就说evil1内部的will-stop?(evil2, evil2)返回的是false，也就是说它告诉我们evil2(evil2)不会停机。但是，别忘了evil1(evil2)和evil2(evil2)代表的其实都是evil(evil)，所以will-stop?的结果自相矛盾了。
那么，反过来呢？假设evil1(evil2)不能停机，则evil1内部的will-stop?(evil2, evil2)必然返回true，也就是说它告诉我们evil2(evil2)停机了。依然还是自相矛盾。
也就是说，无论怎么假设都无法让内部和外部的will-stop?达成一致。因此，我们说，不存在这样一个算法，对于任意一个给定的程序和输入，都可以判定出该程序是否会停机。也就是说，停机问题是不可判定的。
写在后面
证明的部分我参考了Daniel Friedman[2]以及刘未鹏[3]的实现。同时，做了一些表述上的优化，并补充了一些背景知识[4]，使它看起来不像是一个冷冰冰的数学问题。
参考资料
[1] Halting problem
[2] 《The Little Schemer - 4th Edition》
[3] 康托尔、哥德尔、图灵——永恒的金色对角线(rev#2)
[4] 《计算进化史：改变数学的命运》
