递归可枚举语言

在数学、逻辑和计算机科学中，一种形式语言被称为递归可枚举的（也可识别的、部分可判定的、半可判定的、图灵可接受的或图灵可识别的）如果它是 语言，即，如果存在一个图灵机，它将枚举该语言的所有有效字符串。

递归可举语言在乔姆斯基形式语言层次结构中被称为类型 0 语言。 所有常规的、上下文无关的、上下文相关的和递归的语言都是递归可枚举的。

所有递归可枚举语言的类称为 RE。

递归可枚举语言有三个等价的定义：

• 递归可枚举语言是语言字母表中所有可能单词集合中的递归可枚举子集。
• 递归可枚举语言是一种形式语言，其中存在图灵机（或其他可计算函数），它将枚举该语言的所有有效字符串。 请注意，如果语言是无限的，则可以选择提供的枚举算法以避免重复，因为我们可以测试为数字 n 生成的字符串是否已经为小于 n 的数字生成。 如果已经生成，则使用输入 n+1 的输出（递归），但再次测试它是否是新的。
• 递归可枚举语言是一种形式语言，它存在一个图灵机（或其他可计算函数），当以该语言中的任何字符串作为输入时，它会停止并接受，但在出现时可能会停止并拒绝或永远循环 使用不在该语言中的字符串。 将此与递归语言进行对比，递归语言要求图灵机在所有情况下都停止。

所有常规的、上下文无关的、上下文相关的和递归的语言都是递归可枚举的。

波斯特定理表明，RE 及其补码 co-RE 对应于算术层次结构的xxx层。

停止图灵机的集合是递归可枚举的，但不是递归的。 实际上，可以运行图灵机并在机器停止时接受，因此它是递归可枚举的。 另一方面，问题是不可判定的。

其他一些非递归的递归可枚举语言包括：

• 邮政通信问题
• 死亡率（可计算性理论）
• 解决问题

递归可枚举语言 (REL) 在以下操作下关闭。 也就是说，如果 L 和 P 是两种递归可枚举的语言，则以下语言也是递归可枚举的：

• Kleene star L ∗ {displaystyle L{*}} of L
• L 和 P 的串联 L ∘ P {displaystyle Lcirc P}

• 并集 L ∪ P {displaystyle Lcup P}
• 交集 L ∩ P {displaystyle Lcap P} 。

递归可枚举语句在集差或互补下不闭合。 如果 P {displaystyle P} 是递归的，则集差 L {displaystyle L} − P {displaystyle P} 是递归可枚举的。 如果 L {displaystyle L} 是递归可枚举的，那么 L {displaystyle L} 的补集是递归可枚举的当且仅当 L {displaystyle L} 也是递归的。