更新时间：2022-09-07 10:17
递归可枚举语言定义：设S⊆ Σ为一个语言，E是一个枚举器，若L（E） =S，则称E枚举了语言S。若存在这样 的E，S就称为递归可枚举语言。
注意，枚举器E可以以任意的顺序枚举语言L（E），而且L（E） 中的某个串可能会被E多次重复地打印。
图灵可识别语言定义：设是一台图灵机，若在输入串上运行后可进入接受状态并停机，则称接受串。所接受的所有字符串的集合称为所识别的语言，简称的语言，记作。
设是一个语言，若存在图灵机使得，则称图灵机识别，且称为图灵可识别语言。
下列定理揭示了递归可枚举语言和图灵可识别语言的联系。
定理：一个语言是图灵可识别的，当且仅当它是递归可枚举的。
证明：若有枚举器E枚举语言S，构造一个图灵机M如下：
对于输入ω
注意当ω ∉S时，M可能永不停机，但M所接受的语 言集合恰好是S，所以M识别了S。
假设我们有图灵机M识别语言S，构造一个枚举器E如下：
忽略输入
显然，这样构造的枚举器E最终输出的语言恰好就是S。注意S中的字符串并 没有在E中按字典序输出，而且同一个串可能会被E输出多次，但根据枚举器的定义，这些都是允许的。
递归可枚举语言在下列运算下是闭合的。就是说，如果L和P是两个递归可枚举语言，则下列语言也是递归可枚举的：
L的Kleene星号：
L和P的串接：
并集：
交集：
注意递归可枚举语言不闭合于差集和补集之下。
注意图灵可识别语言和图灵可判定语言的区别：若是图灵可识别语言，则只需存在一台图灵机，当的输入时，一定会停机并进入接受状态；当的输入时，可能停机并进入拒绝状态，或者永不停机。而若是图灵可判定语言，则必须存在图灵机，使得对于任意输入串，总能停机，并根据属于或不属于分别进入接受或拒绝状态。
并不是所有的语言都是图灵可识别的，可以证明存在图灵不可识别语言。