递归可枚举语言

递归可枚举语言定义：设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}$ 分别进入接受或拒绝状态。

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

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

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