チューリング機械 M と入力 w の組 (M, w) のうち、M が w に対して停止するもの全体の集合を H とする。H の性質として、正しいものはどれか。

解説

正解は「帰納的可算であるが、帰納的（決定可能）ではない」です。万能チューリング機械で M を入力 w の上で模倣し、停止したら受理すれば、H に属する組は必ず有限時間で受理されるので、H は帰納的可算（半決定可能）です。しかし、停止しない場合は模倣が終わらず、属さないと答えられません。対角線論法により、すべての入力で停止して正しく判定するチューリング機械は存在しないため、帰納的ではありません。「帰納的（決定可能）である」は停止性問題の決定不能性に反します。「帰納的可算でもない」は誤りで、H の補集合がこれに当たります。「正規言語である」は、正規言語はすべて決定可能なので誤りです。