递归可枚举语言

在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-0语言。所有递归可枚举语言的类叫做RE。

形式定义

递归可枚举语言定义：设S ⊆ Σ^*为一个语言，E是一个枚举器，若L（E） = S，则称E 枚举了语言S。若存在这样 的E，S就称为递归可枚举语言。

注意，枚举器E可以以任意的顺序枚举语言L（E），而且L（E） 中的某个串可能会被E多次重复地打印。

图灵可识别语言定义：设${\displaystyle M}$是一台图灵机，若在输入串${\displaystyle \omega }$上${\displaystyle M}$运行后可进入接受状态并停机，则称${\displaystyle M}$接受串${\displaystyle \omega }$。${\displaystyle M}$所接受的所有字符串的集合称为${\displaystyle M}$所识别的语言，简称${\displaystyle M}$的语言，记作${\displaystyle L(M)}$。

设${\displaystyle S\subseteq \Sigma ^{*}}$是一个语言，若存在图灵机${\displaystyle M}$使得${\displaystyle L(M)=S}$，则称图灵机${\displaystyle M}$ 识别${\displaystyle S}$，且${\displaystyle S}$称为图灵可识别语言。

两个定义的等价性

下列定理揭示了递归可枚举语言和图灵可识别语言的联系。

定理：一个语言是图灵可识别的，当且仅当它是递归可枚举的。

证明：若有枚举器E枚举语言S，构造一个图灵机M如下：

M = 对于输入ω

1. 运行E，依次生成字符串s₁, s₂, ...；
2. 若遇到某个s_i = ω则进入接受状态并停机。

注意当ω ∉ S时，M可能永不停机，但M所接受的语 言集合恰好是S，所以M识别了S。

假设我们有图灵机M识别语言S，构造一个枚举器E如下：

E = 忽略输入

1. 对i = 1, 2, 3, ...重复下列步骤；
2. 设Σ^* = {s₁, s₂, ...}，分别将s₁, s₂, ... ,s_i作为M的输入，模拟M执行i步；
3. 若某个s_j, 1 ≤ j ≤ i，在i步内可被M接受，则将其输出。

显然，这样构造的枚举器E最终输出的语言恰好就是S。注意S中的字符串并 没有在E中按字典序输出，而且同一个串可能会被E输出多次，但根据枚举器的定义，这些都是允许的。

闭包性质

递归可枚举语言在下列运算下是闭合的。就是说，如果L和P是两个递归可枚举语言，则下列语言也是递归可枚举的：

• L的Kleene星号${\displaystyle L^{*}}$
• L和P的串接${\displaystyle L\circ P}$
• 并集${\displaystyle L\cup P}$
• 交集${\displaystyle L\cap P}$

注意递归可枚举语言不闭合于差集和补集之下。

图灵可识别语言与图灵可判定语言的关系

注意图灵可识别语言和图灵可判定语言的区别：若${\displaystyle S}$是图灵可识别语言，则只需存在一台图灵机${\displaystyle M}$，当${\displaystyle M}$的输入${\displaystyle \omega \in S}$时，${\displaystyle M}$一定会停机并进入接受状态；当${\displaystyle M}$的输入${\displaystyle \omega \notin S}$时，${\displaystyle M}$可能停机并进入拒绝状态，或者永不停机。而若${\displaystyle S}$是图灵可判定语言，则必须存在图灵机${\displaystyle M}$，使得对于任意输入串${\displaystyle \omega \in \Sigma ^{*}}$，${\displaystyle M}$总能停机，并根据${\displaystyle \omega }$ 属于或不属于 ${\displaystyle S}$分别进入接受或拒绝状态。

并不是所有的语言都是图灵可识别的，可以证明存在图灵不可识别语言。

定理

• 波斯特定理
• 克莱尼–波斯特定理
• 弗里德堡–穆奇尼克定理
• 波斯纳–罗宾逊定理
• 跳躍逆轉定理

参见

• 图灵机
• 枚举器
• 递归语言
• 递归可枚举集合