在数学、逻辑和计算机科学中，递归语言或递迴语言是也叫做可判定语言或图灵可判定语言的形式语言类型。所有递归语言的类经常被称为 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的补都是图灵可识别的。 下面假设存在图灵机M1和M2分别识别S和S的补，我们可以构造一个图灵机M如下：
M= 对于输入 ω
- 对于i= 1, 2, 3, ... 分别重複以下步骤：
- 将 ω 作为M1的输入，模拟运行M1，如果M1可以在i步之内接受 ω，则M进入接受状态并停机；
- 将 ω 作为M2的输入，模拟运行M2，如果M2可以在i步之内接受 ω，则M进入拒绝状态并停机。
很显然，对于任何 ω，它要幺属于S，要幺属于S的补， 所以M1和M2中必然有且仅有一个 可以在有限步执行内接受 ω 。 若M1在k步内接受 ω，说明 ω 属于S， 则当i=k时，M会接受 ω 并停机； 同理，若M2在k步内接受 ω， 说明 ω 属于S的补，则当i=k时，M会拒绝 ω 并停机。于是M就判定了语言S。
根据上述定理直接可得下述引理：
定理：HALTING 的补语言是图灵不可识别的。
证明：很显然 HALTING 是图灵可识别语言，若它的补语言也是图灵可识别的， 则根据上述定理知 HALTING 是图灵可判定的，这和停机问题中证明的结论矛盾。