言語分類（計算）

Question

L:={<M>|HP<=L(M)}が再帰言語で、Lが再帰的に列挙可能な言語であるかどうかを判断する必要があります。

私はLがREにない場合は、Lは、いずれかのRではありません

Answer 1

...ライスの定理がLは再帰的ではありません証明が、私はLが帰納的可算であるとは思わない助けることができると思います。

これを停止問題に減らすようにしてください。 Xは、L（X）が真であれば偽を出力するチューリングマシンであり、L（X）が偽であれば真を出力すると言います。

L（X）は真ですか？ L（X）が偽であれば矛盾です。

L（X）は間違っていますか？ L（X）が真ならば唯一であり、矛盾でもある。

矛盾は、Lがチューリングマシンによって計算可能であるという暗黙の前提にあります。したがって、Lは計算可能ではない。 Xチューリングマシンは存在できません。最後に、LはREにはなく（Rではなく）