查看“︁递归可枚举语言”︁的源代码

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

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

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

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

设<math>S \subseteq \Sigma^*</math>是一个语言，若存在图灵机<math>M</math>使得<math>L(M) = S</math>，则称图灵机<math>M</math> '''识别'''<math>S</math>，且<math>S</math>称为'''图灵可识别语言'''。
===两个定义的等价性===
下列定理揭示了递归可枚举语言和[[图灵可识别语言]]的联系。

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

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

''M'' = 对于输入ω
# 运行''E''，依次生成字符串''s''<sub>1</sub>, ''s''<sub>2</sub>, ...；
# 若遇到某个''s''<sub>i</sub> = ω则进入接受状态并停机。

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

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

''E'' = 忽略输入
# 对''i'' = 1, 2, 3, ...重复下列步骤；
# 设Σ<sup>*</sup> = {''s''<sub>1</sub>, ''s''<sub>2</sub>, ...}，分别将''s''<sub>1</sub>, ''s''<sub>2</sub>, ... ,''s''<sub>i</sub>作为''M''的输入，模拟''M''执行''i''步；
# 若某个''s''<sub>j</sub>, 1 ≤ j ≤ i，在''i''步内可被''M''接受，则将其输出。

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

== 闭包性质 ==

递归可枚举语言在下列运算下是[[闭包 (数学)|闭合]]的。就是说，如果''L''和''P''是两个递归可枚举语言，则下列语言也是递归可枚举的：
* ''L''的[[Kleene星号]]<math>L^*</math>
* ''L''和''P''的[[串接]]<math>L \circ P</math> 
* [[并集]]<math>L \cup P</math>
* [[交集]]<math>L \cap P</math>

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

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

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

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

== 定理 ==
* [[波斯特定理]]
* [[克莱尼–波斯特定理]]
* [[弗里德堡–穆奇尼克定理]]
* [[波斯纳–罗宾逊定理]]
* [[跳躍逆轉定理]]

== 参见 ==

* [[图灵机]]
* [[枚举器]]
* [[递归语言]]
* [[递归可枚举集合]]

{{形式语言与形式文法}}
[[Category:图灵机]]
[[Category:形式语言|D]]