computation - 言語分類（計算）

Question

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

ライスの定理は再帰的ではないことを証明するのに役立つと思いますが、それが帰納的可算であるとはL思いません...L

Answer 1

L が RE にない場合、L は R にもありません。

それを停止問題に減らすようにしてください。X は、L(X) が真の場合に偽を出力し、L(X) が偽の場合に真を出力するチューリング マシンであるとします。

L(X) は真ですか? それは、L(X) が false である場合のみであり、これは矛盾です。

L(X) は偽ですか? それは、L(X) が真である場合のみであり、これも矛盾です。

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