ライスの定理について - Qiita

これは，プログラムの機能（関数）としては同じであるが，プログラム文字列として違うものが存在するということを述べている．例えば，余分なスペースをn個追加するであったり，無害で無意味な操作（$x:=x$などの意味のない代入）をn回繰り返すであったりを元のプログラムに施すことを考えれば明らかである． 決定不能（述語，問題） ※以下に述べることは，停止性問題（Halting Problem）のことなので知っている方はスキップしてください． 指標の章に書いたとおり，プログラムは停止せずに答えが永久に帰ってこないことがありうる．では，あるプログラムの指標を受け取り，「その指標が表すプログラムが，ある自然数の入力に対し，停止するか否か」を事前に判定するプログラム（コンパイラによるチェックに近い）を作ることができるだろうか？ 実は，以下の議論から，そのような停止性を判定するプログラムが作成できないことが判