任意のプログラムxに対して、無限ループするかどうかを
確実に検出するプログラムPが存在すると仮定する。
Pを用いて、次のようなプログラムP'を構成する：
P'は、入力xに対してPを用いて判定し、
(1) xが無限ループするなら停止し、
(2) xが無限ループにならないならわざと無限ループする

さあ、P'の入力として、P'自身を判定させてみよう！
上記のxにP'を代入すると、
(1) P'が無限ループするなら（P'は）停止し、
(2) P'が無限ループにならないなら（P'は）わざと無限ループする

言ってることが完全に矛盾しているので、最初の仮定は誤り。
よって、任意のプログラムに対して、無限ループするかどうかを
確実に検出するプログラムは存在しない。

という証明をこのまえ学校で習いました。