停机问题的不可判定性证明

停机问题问的是：能否设计一个通用算法，输入任意一个程序，判断它最终会不会停止运行？答案被严格证明是否定的，证明思路是自引用式的反证法：假设存在这样一个”停机函数”程序 H，把它的所有变量都初始化成 H 自身的编码，再在末尾加一句”如果判定结果为真就进入死循环”——这个改造后的新程序会陷入一个逻辑死结：如果假设它会停机，运行过程恰恰会证明它陷入死循环（矛盾）；如果假设它不会停机，运行过程恰恰会让它顺利停止（同样矛盾）。因为两种假设都会导向自我否定，唯一站得住脚的结论就是最初”存在这样一个 H”的假设本身是错的。发散：这个证明手法和”这句话是假的”这类自指悖论、以及集合论里”所有不包含自身的集合的集合是否包含自身”如出一辙——把停机问题的不可解性和这些经典悖论对照理解，能看清计算理论里的”不可解”并不是”我们还没找到足够聪明的算法”，而是这类自引用结构本身在逻辑上根本不可能被一致地判定，这是数学结构的硬限制，不是工程能力的欠缺。