递归可枚举语言
维基百科，自由的百科全书
在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-0 语言。所有递归可枚举语言的类叫做 RE。
目录 |
[编辑] 形式定义
递归可枚举语言定义：设 S ⊆ Σ* 为一个语言，E 是一个枚举器， 若 L(E) = S，则称 E 枚举了语言 S。若存在这样 的 E，S 就称为递归可枚举语言。
注意，枚举器 E 可以以任意的顺序枚举语言 L(E) ，而且 L(E) 中的某个串可能会被 E 多次重复地打印。
图灵可识别语言定义：设 M 是一台图灵机，若在输入串 ω 上 M 运行后可进入接受状态并停机，则称 M 接受串 ω。M 所接受的所有字符串的集合称为 M 所识别的语言，简称 M 的语言，记作 L(M)。
设 
是一个语言，若存在图灵机 M 使得 L(M) = S，则称图灵机 M 识别 S，且 S 称为图灵可识别语言。
[编辑] 两个定义的等价性
下列定理揭示了递归可枚举语言和图灵可识别语言的联系。
定理：一个语言是图灵可识别的，当且仅当它是递归可枚举的。
证明：若有枚举器 E 枚举语言 S，构造一个图灵机 M 如下：
M = 对于输入 ω
- 运行 E，依次生成字符串 s1, s2, ...；
- 若遇到某个 si = ω 则进入接受状态并停机。
注意当 ω ∉ S 时，M 可能永不停机，但 M 所接受的语 言集合恰好是 S，所以 M 识别了 S 。
假设我们有图灵机 M 识别语言 S，构造一个枚举器 E 如下：
E = 忽略输入
- 对 i = 1, 2, 3, ... 重复下列步骤；
- 设 Σ* = {s1, s2, ...}，分别将s1, s2, ... ,si 作为 M 的输入，模拟 M 执行 i 步；
- 若某个 sj, 1 ≤ j ≤ i，在 i 步内可被 M 接受，则将其输出。
显然，这样构造的枚举器 E 最终输出的语言恰好就是 S 。注意 S 中的字符串并 没有在 E 中按字典序输出，而且同一个串可能会被 E 输出多次，但根据枚举器的定义， 这些都是允许的。
[编辑] 闭包性质
递归可枚举语言在下列运算下是闭合的。就是说，如果 L 和 P 是两个递归可枚举语言，则下列语言也是递归可枚举的:
注意递归可枚举语言不闭合于差集和补集之下。
[编辑] 图灵可识别语言与图灵可判定语言的关系
注意图灵可识别语言和图灵可判定语言的区别：若 S 是图灵可识别语言，则只需存在一台图灵机M，当 M 的输入 
时，M 一定会停机并进入接受状态；当 M 的输入 
时，M 可能停机并进入拒绝状态，或者永不停机。而若 S 是图灵可判定语言，则必须存在图灵机 M，使得对于任意输入串 
，M 总能停机，并根据 ω 属于或不属于 S 分别进入接受或拒绝状态。
并不是所有的语言都是图灵可识别的，可以证明存在图灵不可识别语言。
[编辑] 参见
| 自动机理论: 形式语言和形式文法 | |||
|---|---|---|---|
| 乔姆斯基层级 | 文法 | 语言 | 极小自动机 |
| 类型 0 | 无限制 | 递归可枚举 | 图灵机 |
| n/a | (无公用名) | 递归 | 判定器 |
| 类型 1 | 上下文有关 | 上下文有关 | 线性有界 |
| n/a | 附标 | 附标 | 嵌套堆栈 |
| n/a | 树-邻接 | 适度上下文有关 | 嵌入下推 |
| 类型 2 | 上下文无关 | 上下文无关 | 非确定下推 |
| n/a | 确定上下文无关 | 确定上下文无关 | 确定下推 |
| 类型 3 | 正则 | 正则 | 有限 |
| 每个语言或文法范畴都是其直接上面的范畴的真子集。 | |||
