停止性問題についての記述として、正しいものはどれか。

解説

正解は「任意のプログラムと入力について、停止するかを判定するアルゴリズムは存在しない」です。仮に判定プログラム H があるとすると、「自分自身を入力として H に問い合わせ、停止すると判定されたら無限ループし、停止しないと判定されたら停止する」プログラム D を作れます。D に D 自身を与えるとどちらの判定でも矛盾するため、H は存在しません。「指数時間をかければ、必ず判定できる」は誤りで、時間をいくらかけても判定できない決定不能な問題です。「非決定性チューリング機械なら、多項式時間で判定できる」も誤りで、非決定性にしても計算できる範囲は変わりません。「有限オートマトンが停止するかどうかも、判定できない」も誤りで、有限オートマトンは入力を読み終えれば必ず停止します。