停止問題が計算できない = 停止問題を解くプログラムが作れないということ = 不完全性定理
これを,停止問題の決定不能性という.

どんなチューリング・マシンでも「無限ループするか/しないか」が分かる,
というチューリング・マシンA(x)をプログラムできたとする.

xは,判定したいチューリング・マシンのことで,A(x)のテープに,xのプログラムとして入力するという意味.

このとき,
A(x):{xが無限ループしないなら1を出力し,無限ループするなら0を出力する}
とする.

次に,A(x)を組み込んで,わざと無限ループするチューリング・マシンB(x)を設計する.
B(x):{A(x) = 1なら無限ループし,A(x) = 0 なら無限ループしない}

B(x)にB(x)を入力すると
B(B(x)) = {A(B(x)) = 1 なら無限ループし, A(B(x)) = 0 なら無限ループしない}

では,チューリング・マシンB(B(x))は,無限ループするか,しないか?

逆に