递归可列举语言

在数学、逻辑学和计算机科学中，如果一种形式语言是该语言字母表上所有可能的词语集合中的一个可递归可列举的子集，也就是说，如果存在一台图灵机可以列举出该语言的所有有效字符串，那么该语言就被称为递归可列举（也是可识别的、部分可解的、半可解的、图灵可接受的或图灵可识别的）。可递归列举的语言在乔姆斯基形式语言的等级体系中被称为0型语言。所有正规的、无语境的、对语境敏感的和递归的语言都是可递归列举的。所有可递归枚举语言的类别被称为RE。定义递归可列举语言有三个等价的定义。递归可列举语言是在该语言的字母表上所有可能的词的集合中的一个递归可列举的子集。递归可列举语言是一种形式语言，对于这种语言存在一个图灵机（或其他可计算的函数），可以列举出该语言的所有有效字符串。请注意，如果语言是无限的，所提供的枚举算法可以被选择，以避免重复，因为我们可以测试为数字n产生的字符串是否已经为一个小于n的数字产生。

递归可列举语言是一种存在图灵机（或其他可计算函数）的形式语言，当输入该语言中的任何字符串时，它将停止并接受，但当输入不在该语言中的字符串时，它可能停止并拒绝或永远循环。这与递归语言形成对比，后者要求图灵机在所有情况下都能停止。所有正规的、无语境的、语境敏感的和递归的语言都是可递归列举的。波斯特定理表明，RE与它的补数co-RE一起，对应于算术层次的xxx层。

终止图灵机的集合是可递归列举的，但不是递归的。事实上，人们可以运行图灵机并接受机器是否停止，因此它是可递归列举的。另一方面，这个问题是不可判定的。其他一些非递归可列举的语言包括。

死亡率(可计算性理论)Entscheidungsproblem封闭属性递归可列举语言(REL)在下列操作下是封闭的。也就是说，如果L和P是两个可递归列举的语言，那么下面的语言也是可递归列举的。递归可列举语言在集差或补足下是不封闭的。集合差分{displaystyleL}{displaystyleP}是可递归枚举的，如果P{displaystyleP}是递归的。是递归的。如果L{displaystyleL}是可递归的。是可递归列举的，那么L的补集L{的补集｝的补集是可递归列举的，当且仅当L{displaystyleL}的补集也是递归的。也是递归的。