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) 为假时，这是一个矛盾。

L(X) 是假的吗？当且仅当 L(X) 为真，这也是一个矛盾。

矛盾在于隐含的假设，即 L 可由图灵机计算。因此 L 是不可计算的。X 图灵机不可能存在。最后 L 不在 RE 中（也不在 R 中）。