世界でもっとも強力な9のアルゴリズム 10章 決定不能性とは何か
現在のソフトウェアは20年くらいまえのソフトウェアとくらべて、クラッシュすること自体は減っており、これは自動テストツール等の発達に依る部分が大きいが、果たして完全なクラッシュ検出プログラムというものを作ることは可能であろうか?
上記の質問に対して、実際には存在しない「入力がクラッシュしないプログラムだった時だけクッシュする」というプログラムを想定することと背理法で証明する。
プログラムの決定不能性や効率性の問題は、単なる思考実験や哲学としてだけではなく、実際のプログラムの限界、というものを知るためにも重要である。