什么是递归语言介绍

在数学、逻辑和计算机科学中，递归语言或递回语言是也叫做可判定语言或图灵可判定语言的形式语言类型。所有递归语言的类经常被称为 R。这种语言类型在乔姆斯基层级中没有定义。

递归语言定义

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

递归语言是在形式语言的字母表上的所有可能的字的集合的递归子集。

设S⊆ Σ是一个语言，M是一台图灵机， 若对于任何字符串 ω ∈ Σ，有

ω ∈S当且仅当M接受 ω

ω ∉S当且仅当M拒绝 ω

则称M判定语言S。 若存在这样的M，S就称为图灵可判定语言。

递归语言闭包性质

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

L的Kleene星号：

L的非删除(non-erasing)同态：φ(L)

L和P的串接：

并集：

交集：

L的补集：

差集：

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

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

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

证明：定义语言 HALTING 如下：

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

其中 <M,x> 表示将M的编码和串x以某种方式配对而得到的串。 可以证明 HALTING 是图灵不可判定语言。

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

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

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

M= 对于输入 ω

对于i= 1, 2, 3, ... 分别重复以下步骤：

将 ω 作为M₁的输入，模拟运行M₁，如果M₁可以在i步之内接受 ω，则M进入接受状态并停机；

将 ω 作为M₂的输入，模拟运行M₂，如果M₂可以在i步之内接受 ω，则M进入拒绝状态并停机。

很显然，对于任何 ω，它要么属于S，要么属于S的补， 所以M₁和M₂中必然有且仅有一个 可以在有限步执行内接受 ω 。 若M₁在k步内接受 ω，说明 ω 属于S， 则当i=k时，M会接受 ω 并停机； 同理，若M₂在k步内接受 ω， 说明 ω 属于S的补，则当i=k时，M会拒绝 ω 并停机。于是M就判定了语言S。

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

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

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