递归可枚举语言
维基百科，自由的百科全书
设 S ⊆ Σ* 为一个语言，E 是一个枚举器， 若 L(E) = S，则称 E 枚举了语言 S。若存在这样 的 E，S 就称为递归可枚举语言。
注意，枚举器 E 可以以任意的顺序枚举语言 L(E) ，而且 L(E) 中的某个串可能会被 E 多次重复地打印。
下列定理揭示了递归可枚举语言和图灵可识别语言的联系。
定理：一个语言是图灵可识别的，当且仅当它是递归可枚举的。
证明：若有枚举器 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 输出多次，但根据枚举器的定义， 这些都是允许的。
