recursion - 如何确定一种语言是递归的还是递归可枚举的？

Question

我必须确定一种语言(例如 L={a^n b^m c^s | 0<=n<=m<=s})是常规的、上下文无关的、递归的、递归可枚举的还是没有的。

我知道如何确定一种语言是正则的(找到有效的 DFA 或正则表达式)还是无上下文的(找到有效的 PDA 或上下文无关的语法)；我知道递归语言有一个总是停止的图灵机，而递归可枚举语言有一个可能不会停止的图灵机。

所以问题是:是否有一个快速的标准来确定语言是递归的还是递归可枚举的，或者两者都不是？例如，我不必构建 PDA 来理解一种语言是上下文无关的，我无法通过它需要一个堆栈来理解它；是否有类似的快速方法来解决这个问题(希望可以省去构建图灵机的麻烦)？

Answer 1

没有结构化的方法来检查语言是递归还是递归可枚举。实际上有一个很酷的证据表明，对于任何能够识别递归语言的自动机，至少有一种 R 语言以外的 RE 语言被自动机接受；它是您用来显示不可判定问题存在的对角化论证的变体。

证明一种语言是 RE 而不是 R 的主要方法是证明该语​​言是 RE(也许通过为它定义一个 TM)，然后将 RE 中的已知问题而不是 R 简化为该问题。例如，如果您可以证明任何停机问题的实例都可以通过将其转换为您的问题的实例来解决，那么您就知道它不能有递归解决方案，并且如果您使用 TM 来解决这个问题语言，您知道该语言是在 RE 中。总之，您在 RE 中有一种语言，但在 R 中没有。