計算可能性

「アート・オブ・プロジェクトマネジメント」を読んでいて、「NP完全問題を多項式時間内に解決する」という記述から、学生時代に勉強した、プログラムの停止性を判断できるプログラムは存在しない、の証明を思い出しました。

つまり、任意のプログラムが停止するかどうか判断するプログラムは存在しない、ということです。

まず前提条件として、任意のプログラムの停止性を判断できるプログラムがあったとします。

このプログラムを次のように修正します。

入力のプログラムが停止する場合は無限ループにして停止しないようにする。

また停止しないとわかった場合は、そこで停止するようにする。

次に、このプログラム自身を入力として、そのプログラムに入力する。

すると、このプログラムが停止する場合は、このプログラムは停止しない。

このプログラムが停止しない場合は、このプログラムは停止する。

矛盾です。

つまり前提が間違っている。

任意のプログラムの停止性を判断するプログラムは存在しない。

以上。

ポイントは、自分を自分に食わせること。

「ゲーデルの不完全性定理」も基本的に、このテクニックで証明します。