計算できない問題・関数についていくつかの問題 停止問題 プログラムを実行すると、 実行が終了して停止するか停止せずにいつまでも実行を続けるかの、 どちらかになる。 そこで、与えられたプログラムが停止するか、 いつまでも停止しないかを判定する、 という問題(プログラムの「停止問題」という)を考える。 (この問題をちゃんとした問題として扱うには、 プログラムがどう実行されるのかが 正確に(処理系依存とかのあいまいさ無しに)定義されている必要がある。 だから普通は、チューリングマシンみたいな できるだけ単純な道具立てを使って話をする。 でも、ここでは細かい事にはこだわらず、 「適当にどうにか定義してある」事にしておく。) 停止問題を解くプログラムを作りたいとする。 これは、コンパイラと比較すると判りやすいかもしれない。 コンパイラはプログラム(のソース)を受けとり、 実行コードを出力する。 停止問題を解くプログラムは、 プロ
