停止問題が計算できない = 停止問題を解くプログラムが作れないということ = 不完全性定理
これを,停止問題の決定不能性という.
どんなチューリング・マシンでも「無限ループするか/しないか」が分かる,
というチューリング・マシン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))は,無限ループするか,しないか?
- 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))という自己言及的なチューリング・マシンは,計算結果を決定できない.
参考文献
量子コンピューターが本当にすごい