停机问题的不可判定性

命题陈述

不存在这样的算法:对任意给定的程序(图灵机)$P$ 与输入 $x$,总能在有限时间内正确判断 $P$ 在输入 $x$ 上运行是否会停机。

为什么成立?

假设存在这样的停机判定器 $H$。构造一个程序 $D$:对输入的程序 $Q$,先用 $H$ 检查 $Q$ 在以自身为输入运行时是否停机,然后做相反的事(若 $Q$ 停机则死循环,若 $Q$ 死循环则停机)。把 $D$ 自身作为输入运行,无论哪种情形都会导致矛盾,因此 $H$ 不可能存在。

用到此定理的主题

相关定理

分步证明

该定理暂无分步证明。