递归可枚举(Recursively Enumerable)语言

与 图灵可识别(Recognizable)语言 的形式定义

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

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

图灵可识别语言定义：设 M是一台图灵机，若在输入串ω上M运行后可进入接受状态并停机，则称M接受串ω。M所接受的所有字符串的集合称为M所识别的语言，简称 M的语言，记作L(M)。

设 S ⊆ Σ* 是一个语言，若存在图灵机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输出多次，但根据枚举器的定义，这些都是允许的。

图灵可识别(Recognizable)语言

与 图灵可判定(Decidable)语言 的关系

注意图灵可识别语言和图灵可判定语言的区别：若S是图灵可识别语言，则只需存在一台图灵机M，当 M的输入ω ∈ S时，M一定会停机并进入接受状态；当M的输入ω ∉ S时，M可能停机并进入拒绝状态，或者永不停机。

而若S是图灵可判定语言，既递归(Recursive)语言，则必须存在图灵机M，使得对于任意输入串ω ⊆ Σ*，M总能停机，并根据ω属于或不属于S分别进入接受或拒绝状态。

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

停机问题

停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。

该问题等价于如下的判定问题：给定一个程序P和输入w，程序P在输入w下是否能够最终停止（而不是进入无限循环）。

用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个ω ∈ S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的（countable）S 也是可停机的。

艾伦·图灵在1936年用对角论证法证明了，不存在解决停机问题的通用算法。

邱奇-图灵(Church-Turing)论题

邱奇-图灵论题认为“任何在算法上可计算的问题同样可由图灵机计算”

另外一种说法就是逻辑和数学中的有效或机械方法可由图灵机来表示。通常我们假定这些方法必须满足以下的要求：

1.一个方法由有限多简单和精确的指令组成，这些指令可由有限多的符号来描述。

2.该方法总会在有限的步骤内产生出一个结果。

3.基本上人可以仅用纸张和铅笔来执行。

4.该方法的执行不需人类的智慧来理解和执行这些指令。

此类方法的一个范例便是用欧几里得辗转相除法确定两个自然数的最大公约数。

例题

设当前有递归语言 L，其可接纳的字符串集为 Σ。求证：L的补集：Σ*\L 也为递归语言。

证明过程：

因为L是递归语言，则存在一台图灵机M1，能够完成：

1.当且仅当ω ∈ Σ*且 ω ∈ L 时，接受输入串ω并总能进入停机状态，该停机状态为最终态。

2.当且仅当ω ∈ Σ* 且 ω ∉ L 时，拒绝输入串ω并总能进入停机状态，该停机状态为非最终态。

现在通过将M1的最终态与非最终态互换（原本的非最终态变为最终态，最终态变为非最终态），构造另一台图灵机M2。则M2能够完成：

1.当且仅当ω ∈ Σ*且 ω ∈ Σ*\L 时，接受输入串ω并总能进入停机状态，该停机状态为最终态。

2.当且仅当ω ∈ Σ* 且 ω ∉ Σ*\L 时，拒绝输入串ω并总能进入停机状态，该停机状态为非最终态。

故M1拒绝的输入将被M2接受，M1接受的输入将被M2拒绝。

则M2恰好接受 Σ*\L ， 即 Σ*\L 也为递归语言。