語言分類（計算）

Question

我需要確定L:={<M>|HP<=L(M)}是否是遞歸語言，並且L是遞歸可枚舉語言。

我認爲，賴斯的定理可以幫助證明L不是遞歸的，但我不認爲這是L遞歸可枚舉...

Answer 1

如果L不稀土則L不是R中任一。

您應該嘗試將其降低到暫停問題。假設X是一個圖靈機，如果L（X）爲真則輸出false，如果L（X）爲假則輸出真。

L（X）是否爲真？當且僅當L（X）是假的，這是矛盾的。

L（X）是否爲假？當且僅當L（X）是真的，這也是矛盾的。

矛盾在於隱含假設L可以由圖靈機計算。因此L不可計算。 X圖靈機不能存在。最後，L不在RE中（也不在R中）。