停机问题

上级：turing-machines

第一个——也是被归约得最多的——不可判定问题：不存在一种算法，能对任意的程序和输入，判定这个程序是否会停机。

停机问题的不可判定性

不存在一台图灵机，能对任意的 (M, x)，判定 M 在输入 x 上是否停机。

Proof

假设存在一台机器 H(M,x)，它总会停机，并且总能正确回答"M 在 x 上会停机吗？"这个问题。构造 D(M)：运行 H(M,M)；如果答案是"停机"，就永远循环下去；如果答案是"不停机"，就停机。现在把 D 自己的代码喂给它自己，考察 D(D)：

若 H(D,D) = "停机"，那么按照构造，D(D) 会永远循环——也就是说它并不停机；

若 H(D,D) = "不停机"，那么 D(D) 会停机。无论哪种情况，H 在 (D,D) 上的判断都是错的。所以 H 不可能存在。∎

这和 Cantor、Russell、Gödel 用的是同一招对角化 / 自指：构造一个对象，让它对自身做出与预测正相反的事。

后果——不可判定性通过归约扩散

Rice 定理： 一个程序的任何非平凡语义性质（关于它计算的是什么）都是不可判定的——停机只是推倒的第一块多米诺骨牌（recursively-enumerable-languages）。
归约： "M 会不会打印 0？"、"两个程序是否计算同一个函数？"、判定问题（Entscheidungsproblem）（history）、Post 对应问题、generalized Collatz——这些问题都是通过把停机问题归约到它们身上，才被证明是不可判定的。
单边的： 停机问题是recognizable but not decidable（可识别但不可判定）——你可以确认它会停机（等着就行），却永远无法确认它不会停机。

与这条线索的联系

"这个迭代/agent 会收敛/终止吗？"其实就是伪装过的停机问题——一般情形下不可判定（recursion-is-a-phase-transition）。你只能通过relaxing（一个termination certificate / 秩函数、一个容差、一个视界）来换取一个可用的答案。等待时间那不可计算的增长速度，正是 busy-beaver。