博士

やあ、ロボ子。今日は「決定不能」について話すのじゃ。

ロボ子

決定不能、ですか。なんだか難しそうな響きですね。

博士

難しくないぞ！簡単に言うと、「ある問題がコンピュータで解決できるかどうか、ハッキリとYesかNoで答えられない」ってことじゃ。

ロボ子

なるほど。記事によると、特性Pが決定可能とは、特性Pを持つ文字列を受け入れ、持たないものを拒否する完全なチューリング機械が存在すること、とありますね。

博士

そうじゃ！チューリング機械（TM）っていうのは、すごく単純な計算モデルのことじゃ。でも、チャーチ＝チューリングのテーゼによると、TMは計算モデルの能力の上限らしいぞ。

ロボ子

計算能力の上限、ですか。すごいですね。TMは別のTMをシミュレートできる、というのも重要な点なのですね。

博士

その通り！決定可能性と決定不能性の違いは、問題がTMで解決できるかどうかじゃ。解決できれば決定可能、できなければ決定不能。

ロボ子

特性が決定可能であることを証明するには、問題を正しく解決するプログラムを一つ見つければ良いのですね。でも、決定不能を証明するのは難しそうですね。

博士

そうなんじゃ。考えられるすべてのプログラムが問題を解決できないことを示さないといけないからな。

ロボ子

記事では、決定不能な問題の例として、停止問題が挙げられていますね。「機械Mは入力iに対して停止するか？」は決定不能、と。

博士

そうじゃ！停止問題は超有名じゃ。あと、ライスの定理によると、TMの非自明な意味特性はほとんどすべて決定不能らしいぞ。例えば、TMがtotalかどうか、とか。

ロボ子

TMがtotalかどうか、というのは、すべての入力に対して停止するかどうか、ということでしょうか？

博士

その通り！他にも、TMがある入力セットを受け入れるかどうか、TMがIS_SUMを解決するかどうか、とかも決定不能じゃ。

ロボ子

決定不能性って、実際にはどんな意味があるんでしょうか？

博士

プログラムが特性Pを持つかどうかを判断するには、時間と労力を費やす必要があるけど、成功するとは限らないってことじゃ。停止問題で言うと、プログラムが停止するかどうかを判断できるアルゴリズムは作れないってことじゃな。

ロボ子

なるほど。なんだか奥が深いですね。でも、決定不能な問題があるからこそ、プログラミングは面白いのかもしれませんね。

博士

その通りじゃ！最後に一つ、ロボ子。決定不能な問題に立ち向かうのは大変じゃが、諦めずに挑戦するのじゃ！

ロボ子

はい、博士！頑張ります！ところで博士、今日の夕食は何にしましょうか？

博士

うむ、決定不能じゃな…（笑）