[科普中国]-图灵可识别语言-

在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-0语言。所有递归可枚举语言的类叫做RE。

简介在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-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输出多次，但根据枚举器的定义，这些都是允许的。

图灵可识别语言与图灵可判定语言的关系注意图灵可识别语言和图灵可判定语言的区别：若S是图灵可识别语言，则只需存在一台图灵机M，当M的输入时，M一定会停机并进入接受状态；当M的输入时，M可能停机并进入拒绝状态，或者永不停机。而若S是图灵可判定语言，则必须存在图灵机M，使得对于任意输入串，M总能停机，并根据Ω属于或不属于S分别进入接受或拒绝状态。

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

参见图灵机

枚举器

递归语言

递归可枚举集合

本词条内容贡献者为:

王宁 - 副教授 - 西南大学