ある問題 X が決定不能であることを、停止性問題を用いて示す方法として、適切なものはどれか。

解説

正解は「X を解くアルゴリズムがあれば停止性問題も解けることを示す」です。これを、停止性問題を X に帰着するといいます。停止性問題はどんなアルゴリズムでも解けないことが分かっているので、X が解けると仮定すると矛盾が生じ、X も決定不能だと結論できます。「停止性問題を解くアルゴリズムがあれば X も解けることを示す」は帰着の向きが逆で、X が停止性問題より難しくないことしか分からず、X が決定不能であることは示せません。「X を解く指数時間のアルゴリズムを示す」は、逆に X が決定可能であることを示しています。「X が NP 完全であることを示す」は計算の難しさの議論で、NP 完全問題はすべて決定可能です。