Wiki. 停机问题 [停机问题]

假设存在程序 $H$ 满足 $$ H(P,I) := \begin{cases} 1 & P(I) \downarrow\\ 0 & P(I) \uparrow. \end{cases} $$

构造程序 $H^+$, 满足对任意程序 $P$, $$ H^+(P) \downarrow \quad\Leftrightarrow\quad P(P) \uparrow. $$

令 $P=H^+$, 则有 $$ H^+(H^+) \downarrow\,\Leftrightarrow H^+(H^+) \uparrow, $$ 矛盾.