定义

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

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

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

ω ∈ S 当且仅当 M 接受 ω

ω ∉ S 当且仅当 M 拒绝 ω

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

闭包性质

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

L 的Kleene星号 L ∗ ∗ --> {\displaystyle L^{*}}

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

L 和 P 的串接 L ∘ ∘ --> P {\displaystyle L\circ P}

并集 L ∪ ∪ --> P {\displaystyle L\cup P}

交集 L ∩ ∩ --> P {\displaystyle L\cap P}

L 的补集 L C {\displaystyle L^{C}\,}

差集 L − − --> P {\displaystyle L-P\,}

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

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

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

证明： 定义语言 HALTING 如下：

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

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

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

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

M = 对于输入 ω

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

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

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

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

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

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

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

参见

图灵机

判定器

递归集合

递归可枚举语言

停机问题

可判定性

不可判定性

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。