递归可枚举语言

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

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

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

图灵可识别语言定义：设${\displaystyle M}$枚举语言，构造一个图灵机如下：

= 对于输入ω

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

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

= 忽略输入

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

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

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

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

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