遞歸語言

在數學、邏輯和計算機科學中，遞歸語言或遞迴語言是也叫做可判定語言或圖靈可判定語言的形式語言類型。所有遞歸語言的類經常被稱為 R。這種語言類型在喬姆斯基層級中沒有定義。

定義

遞歸語言有兩種等價的主要定義:

遞歸語言是在形式語言的字母表上的所有可能的字的集合的遞歸子集。

設 S ⊆ Σ^* 是一個語言，M 是一台圖靈機，若對於任何字符串 ω ∈ Σ^*，有

ω ∈ S 若且唯若 M 接受 ω
ω ∉ S 若且唯若 M 拒絕 ω

則稱 M 判定語言 S。若存在這樣的 M，S 就稱為圖靈可判定語言。

閉包性質

遞歸語言是在下列運算下是閉合的。就是說，如果 L 和 P 是兩個遞歸語言，則下列語言也是遞歸的:

L 的Kleene星號 $L^{*}$
L的非刪除(non-erasing)同態 φ(L)
L 和 P 的串接 $L\circ P$
併集 $L\cup P$
交集 $L\cap P$
L 的補集 $L^{C}\,$
差集 $L-P\,$

圖靈可判定語言與圖靈可識別語言的關係

注意圖靈可判定語言和圖靈可識別語言的區別：若 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.

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

定理： HALTING 的補語言是圖靈不可識別的。

證明： 很顯然 HALTING 是圖靈可識別語言，若它的補語言也是圖靈可識別的，則根據上述定理知 HALTING 是圖靈可判定的，這和停機問題中證明的結論矛盾。

參見