递归可枚举语言

由自动机处理的最广泛的语言类别是递归可枚举语言（RE语言）——即能被图灵机识别的语言。我们还将探讨RE语言中的一些重要子类。大多数具有实际用途的语言都属于RE语言的一个子集，称为递归语言。此外，我们将完全解除重写系统的限制，从而得到能够生成递归可枚举语言的文法。

递归可枚举语言的定义

递归可枚举语言是指存在一个对应的图灵机，该图灵机能识别且仅识别该语言中的所有字符串。当输入的字符串不属于该语言时，图灵机可能“挂起”（无限运行下去）。

这里的“识别”一词至关重要。若图灵机在处理某个输入字符串时停机并进入接受状态，则称其识别了该字符串。所有此类字符串的集合构成了该图灵机所对应的语言。如果输入字符串不在语言中，图灵机可能（较少见地）停机并拒绝它，或者更有可能陷入无限循环（“挂起”）。换句话说，图灵机能在看到属于语言的字符串时识别出来，但无法总是判断一个字符串不属于该语言。这是由于图灵机并不总能停机所致。目前为止我们所见到的所有语言，都是由总是停机的图灵机来识别的（即这些语言被图灵机“判定”）。我们需要构造一些特殊的例子，才能得到一个递归可枚举但不是递归的语言。

递归语言的定义

递归语言是指存在一个对应的图灵机，能够对所有输入字符串做出判定。该图灵机总是会停机，明确接受语言内的所有字符串，并拒绝不属于该语言的所有字符串。

换言之，存在一种算法可以判定任意给定字符串是否属于某个递归语言。我们说该图灵机“判定”了这个语言，而不仅仅是“识别”它。

记住：递归可枚举语言有图灵机进行识别（对于语言外的字符串可能会挂起）；递归语言则有图灵机总是停机并对每个字符串做出判定。

由于递归语言的图灵机会识别语言中的每一个字符串，因此所有递归语言天然也是递归可枚举的，即递归语言是递归可枚举语言的一个真子集。

一个非递归但递归可枚举的语言示例

为了理解什么是递归可枚举但非递归的语言，假设我们刚刚在社交媒体上发布了一条公开动态。现在考虑这样一个语言：它包含将来某时刻会对这条动态做出回应的所有用户的身份标识（用户名、邮箱或其他唯一标识字符串）。注意这里使用的是将来时态。如果我们拿到某个社交平台用户的任意身份标识，我们可能需要永远等待才能知道他是否会回应。我们只能确认那些已经回应过的人。由于这种定义方式，该语言是不可判定的。

上下文有关语言

嵌套在递归语言类别之内的是上下文有关语言。上下文有关语言是指：判定该语言所需的图灵机磁带空间大小是有界的。语言 $\{a^nb^nc^n\}$ 和 $\{n_a(w)=n_b(w)=n_c(w)\}$ 都属于上下文有关语言。在这两种情况下，所使用的磁带空间等于输入字符串的长度，再加上字符串两端用于空白符号的若干单元格。如果一台图灵机所使用的磁带长度不超过输入长度的某个常数倍，则称其为线性有界自动机（LBA）。下表总结了我们目前关于递归可枚举语言的讨论结果。每一类语言都是其下方类别的超集。

递归可枚举语言的性质

接下来我们探讨递归可枚举语言的一些关键性质，以完善我们对形式语言体系的理解。

首先，递归语言在补运算下是封闭的。这是因为：若语言 $L$ 是递归的，则存在一台图灵机 $M$ 能够判定它。要判定其补语言 $\overline{L}$，我们只需将 $M$ 的输出结果取反即可，如下图所示的机器 $M'$ 所示。

记住：递归语言在补运算下封闭。

现在假设语言 $L$ 及其补语言 $\overline{L}$ 都是递归可枚举的。这意味着存在两台图灵机 $M$ 和 $M'$，分别识别这两个语言。我们可以构造一台新的图灵机 $M^*$，让它并行运行这两台机器。（见下图）

并行运行指的是采用协作式多任务机制，让两台机器轮流执行一条指令：

1重复执行：
2    M 执行下一条指令
3    若 M 停机，则停机并接受
4    M' 执行下一条指令
5    若 M' 停机，则停机并拒绝

任一输入字符串必然属于 $L$ 或 $\overline{L}$ 之一，因此其中一台机器必定会停机。如果字符串使 $M$ 停机并接受，则 $M^*$ 接受该字符串；如果使 $M'$ 停机并接受，则 $M^*$ 拒绝该字符串。因此，机器 $M^*$ 能够判定语言 $L$，这说明 $L$ 和 $\overline{L}$ 都是递归语言！

记住：若一个语言及其补语言都是递归可枚举的，则它们都是递归语言。

由此我们可以得出结论：递归可枚举语言在补运算下不封闭。如果它们在补运算下封闭，那么所有递归可枚举语言都将变成递归语言！

注意：递归可枚举语言在补运算下不封闭。

这意味着：一个非递归的递归可枚举语言，其补语言甚至都不是递归可枚举的——这确实非常奇特！

由于递归可枚举语言在补运算下不封闭，因此它们在集合差运算下也不封闭，因为集合差运算是基于补运算定义的。