停止問題の決定不能性

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

---

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))は,無限ループするか,しないか?

• B(x)が無限ループしないなら,A(B(x) = 0.
• しかし, A(B(x)) = 0 ということは, B(x)は無限ループしている.
• B(x)が無限ループするということは,どんなチューリング・マシンxをB(x)に入力しても無限ループするので, B(B(x))も無限ループする.
• 矛盾

逆に

• B(B(x))が無限ループするなら,A(B(x)) = 1.
• しかし, A(B(x)) = 1 ということは, B(x)は無限ループしていない.
• B(x)が無限ループしないということは,どんなチューリング・マシンxをB(x)に入力しても無限ループしないので, B(B(x))も無限ループしない.
• 矛盾

つまり, B(B(x))という自己言及的なチューリング・マシンは,計算結果を決定できない.

参考文献

量子コンピューターが本当にすごい Google、NASAで実用が始まった“夢の計算機” (PHP新書)