形式定义

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

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

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

设 S ⊆ ⊆ --> Σ Σ --> ∗ ∗ --> {\displaystyle S\subseteq \Sigma ^{*}} 是一个语言，若存在图灵机 M {\displaystyle M} 使得 L ( M ) = S {\displaystyle L(M)=S} ，则称图灵机 M {\displaystyle M} 识别 S {\displaystyle S} ，且 S {\displaystyle S} 称为 图灵可识别语言 。

两个定义的等价性

下列定理揭示了递归可枚举语言和图灵可识别语言的联系。

定理： 一个语言是图灵可识别的，当且仅当它是递归可枚举的。

证明： 若有枚举器 E 枚举语言 S ，构造一个图灵机 M 如下：

M = 对于输入ω

运行 E ，依次生成字符串 s 1 , s 2 , ...；

若遇到某个 s i = ω则进入接受状态并停机。

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

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

E = 忽略输入

对 i = 1, 2, 3, ...重复下列步骤；

设Σ = { s 1 , s 2 , ...}，分别将 s 1 , s 2 , ... , s i 作为 M 的输入，模拟 M 执行 i 步；

若某个 s j , 1 ≤ j ≤ i，在 i 步内可被 M 接受，则将其输出。

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

闭包性质

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

L 的Kleene星号 L ∗ ∗ --> {\displaystyle L^{*}}

L 和 P 的串接 L ∘ ∘ --> P {\displaystyle L\circ P}

并集 L ∪ ∪ --> P {\displaystyle L\cup P}

交集 L ∩ ∩ --> P {\displaystyle L\cap P}

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

图灵可识别语言与图灵可判定语言的关系

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

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

参见

图灵机

枚举器

递归语言

递归可枚举集合

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。