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

在[[数学]]、[[逻辑]]和[[计算机科学]]中，'''递归语言'''或'''遞迴語言'''是也叫做'''可判定语言'''或'''图灵可判定语言'''的[[形式语言]]类型。所有递归语言的类经常被称为 '''[[R (复杂性)|R]]'''。这种语言类型在[[乔姆斯基谱系|乔姆斯基层级]]中没有定义。

==定义==

递归语言有两种等价的主要定义:

'''递归语言'''是在[[形式语言]]的[[字母表 (计算机科学)|字母表]]上的所有可能的字的[[集合 (数学)|集合]]的[[递归集合|递归]][[子集]]。

设 ''S'' &sube; &Sigma;<sup>*</sup> 是一个语言，''M'' 是一台[[图灵机]]，
若对于任何字符串 &omega; &isin; &Sigma;<sup>*</sup>，有
# &omega; &isin; ''S'' 当且仅当 ''M'' 接受 &omega;
# &omega; &notin; ''S'' 当且仅当 ''M'' 拒绝 &omega;
则称 ''M'' '''[[判定器|判定]]'''语言 ''S''。
若存在这样的 ''M''，''S'' 就称为'''图灵可判定语言'''。

== 闭包性质 ==

递归语言是在下列运算下是[[闭包 (数学)|闭合]]的。就是说，如果 ''L'' 和 ''P'' 是两个递归语言，则下列语言也是递归的:
* ''L'' 的[[Kleene星号]] <math>L^*</math>
* ''L''的非删除(non-erasing)[[同态]] φ(L)
* ''L'' 和 ''P'' 的[[串接]] <math>L \circ P</math>
* [[并集]] <math>L \cup P</math>
* [[交集]] <math>L \cap P</math>
* ''L'' 的[[补集]] <math>L^C \,</math>
* [[差集]] <math>L - P \,</math>

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

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

'''定理：'''存在图灵不可判定语言。

'''证明：''' 定义语言 HALTING 如下：

::HALTING = { <''M'', ''x''> | ''M'' 是一台图灵机，''x''是一个字符串，且''M''在输入''x''上可以停机}

其中  <''M'', ''x''> 表示将  ''M'' 的编码和串 ''x'' 以某种方式[[配对函数|配对]]而得到的串。
可以证明 HALTING 是图灵不可判定语言，参见[[停机问题]]。 Q.E.D.

下列定理表明了图灵可判定语言和[[图灵可识别语言]]的关系。

'''定理：'''一个语言是图灵可判定的当且仅当它和它的[[补语言]]都是图灵可识别的。

'''证明：''' 若 ''S'' 是图灵可判定的，显然 ''S'' 和 ''S'' 的补都是图灵可识别的。
下面假设存在图灵机 ''M''<sub>1</sub> 和 ''M''<sub>2</sub> 分别识别''S'' 和 ''S'' 的补，我们可以构造一个图灵机 ''M'' 如下：

''M'' = 对于输入 &omega;
# 对于 ''i'' = 1, 2, 3, ... 分别重复以下步骤：
# 将 &omega; 作为 ''M''<sub>1</sub> 的输入，模拟运行 ''M''<sub>1</sub>，如果  ''M''<sub>1</sub> 可以在 ''i'' 步之内接受 &omega;，则 ''M'' 进入接受状态并停机；
# 将 &omega; 作为 ''M''<sub>2</sub> 的输入，模拟运行 ''M''<sub>2</sub>，如果 ''M''<sub>2</sub>可以在 ''i'' 步之内接受 &omega;，则 ''M'' 进入拒绝状态并停机。

很显然，对于任何 &omega;，它要么属于''S''，要么属于 ''S'' 的补，
所以 ''M''<sub>1</sub> 和 ''M''<sub>2</sub> 中必然有且仅有一个
可以在有限步执行内接受 &omega; 。
若 ''M''<sub>1</sub> 在 ''k'' 步内接受 &omega;，说明 &omega; 属于 ''S''，
则当 ''i'' = ''k'' 时，''M'' 会接受 &omega; 并停机；
同理，若 ''M''<sub>2</sub> 在 ''k'' 步内接受 &omega;，
说明 &omega; 属于 ''S'' 的补，则当 ''i'' = ''k'' 时，
''M'' 会拒绝 &omega; 并停机。于是 ''M'' 就判定了语言 ''S''。 Q.E.D.

根据上述定理直接可得下述引理：

'''定理：''' HALTING 的补语言是图灵不可识别的。

'''证明：'''  很显然 HALTING 是图灵可识别语言，若它的补语言也是图灵可识别的，
则根据上述定理知 HALTING 是图灵可判定的，这和[[停机问题]]中证明的结论矛盾。

== 参见 ==

* [[图灵机]]
* [[判定器]]
* [[递归集合]]
* [[递归可枚举语言]]
* [[停机问题]]
* [[可判定性]]
* [[不可判定性]]

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