更新时间：2022-09-16 16:03
递归语言有两种等价的主要定义：
递归语言是在形式语言的字母表上的所有可能的字的集合的递归子集。
设S⊆ Σ是一个语言，M是一台图灵机， 若对于任何字符串 ω ∈ Σ，有
则称M判定语言S。 若存在这样的M，S就称为图灵可判定语言。
L的补集：
差集：
注意图灵可判定语言和图灵可识别语言的区别：若S是图灵可识别语言，则只需存在一 台图灵机M，当M的输入 ω ∈S时，M一定会 停机并进入接受状态；当M的输入 ω ∉S时，M可能停 机并进入拒绝状态，或者永不停机。而若S是图灵可判定语言，则必须存在图灵机M， 使得对于任意输入串 ω ∈ Σ，M总能停机，并根据 ω 属于或不属于S分别进入接受或拒绝状态。
定理：存在图灵不可判定语言。
证明：定义语言 HALTING 如下：
其中
下列定理表明了图灵可判定语言和图灵可识别语言的关系。
定理：一个语言是图灵可判定的当且仅当它和它的补语言都是图灵可识别的。
证明：若S是图灵可判定的，显然S和S的补都是图灵可识别的。 下面假设存在图灵机M1和M2分别识别S和S的补，我们可以构造一个图灵机M如下：
M= 对于输入 ω
很显然，对于任何 ω，它要么属于S，要么属于S的补， 所以M1和M2中必然有且仅有一个 可以在有限步执行内接受 ω 。 若M1在k步内接受 ω，说明 ω 属于S， 则当i=k时，M会接受 ω 并停机； 同理，若M2在k步内接受 ω， 说明 ω 属于S的补，则当i=k时，M会拒绝 ω 并停机。于是M就判定了语言S。
根据上述定理直接可得下述引理：
定理：HALTING 的补语言是图灵不可识别的。
证明：很显然 HALTING 是图灵可识别语言，若它的补语言也是图灵可识别的， 则根据上述定理知 HALTING 是图灵可判定的，这和停机问题中证明的结论矛盾。