图灵可判定语言

维基百科，自由的百科全书

即递归语言或遞迴語言。

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

ω ∈ S 当且仅当 M 接受 ω
ω ∉ S 当且仅当 M 拒绝 ω

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

注意图灵可判定语言和图灵可识别语言的区别：若 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 是图灵不可判定语言，参见停机问题。 Q.E.D.

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

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

证明： 若 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。 Q.E.D.