遞歸可枚舉語言

在數學、邏輯和計算機科學中，遞歸可枚舉語言是也叫做部分可判定語言或圖靈可識別語言的形式語言類型。它在形式語言的喬姆斯基層級中叫做類型-0語言。所有遞歸可枚舉語言的類叫做RE。

形式定義

遞歸可枚舉語言定義：設S ⊆ Σ^*為一個語言，E是一個枚舉器，若L（E） = S，則稱E 枚舉了語言S。若存在這樣 的E，S就稱為遞歸可枚舉語言。

注意，枚舉器E可以以任意的順序枚舉語言L（E），而且L（E） 中的某個串可能會被E多次重複地打印。

圖靈可識別語言定義：設${\displaystyle M}$是一台圖靈機，若在輸入串${\displaystyle \omega }$上${\displaystyle M}$運行後可進入接受狀態並停機，則稱${\displaystyle M}$接受串${\displaystyle \omega }$。${\displaystyle M}$所接受的所有字符串的集合稱為${\displaystyle M}$所識別的語言，簡稱${\displaystyle M}$的語言，記作${\displaystyle L(M)}$。

設${\displaystyle S\subseteq \Sigma ^{*}}$是一個語言，若存在圖靈機${\displaystyle M}$使得${\displaystyle L(M)=S}$，則稱圖靈機${\displaystyle M}$ 識別${\displaystyle S}$，且${\displaystyle S}$稱為圖靈可識別語言。

兩個定義的等價性

下列定理揭示了遞歸可枚舉語言和圖靈可識別語言的聯繫。

定理：一個語言是圖靈可識別的，若且唯若它是遞歸可枚舉的。

證明：若有枚舉器E枚舉語言S，構造一個圖靈機M如下：

M = 對於輸入ω

1. 運行E，依次生成字符串s₁, s₂, ...；
2. 若遇到某個s_i = ω則進入接受狀態並停機。

注意當ω ∉ S時，M可能永不停機，但M所接受的語 言集合恰好是S，所以M識別了S。

假設我們有圖靈機M識別語言S，構造一個枚舉器E如下：

E = 忽略輸入

1. 對i = 1, 2, 3, ...重複下列步驟；
2. 設Σ^* = {s₁, s₂, ...}，分別將s₁, s₂, ... ,s_i作為M的輸入，模擬M執行i步；
3. 若某個s_j, 1 ≤ j ≤ i，在i步內可被M接受，則將其輸出。

顯然，這樣構造的枚舉器E最終輸出的語言恰好就是S。注意S中的字符串並 沒有在E中按字典序輸出，而且同一個串可能會被E輸出多次，但根據枚舉器的定義，這些都是允許的。

閉包性質

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

• L的Kleene星號${\displaystyle L^{*}}$
• L和P的串接${\displaystyle L\circ P}$
• 併集${\displaystyle L\cup P}$
• 交集${\displaystyle L\cap P}$

注意遞歸可枚舉語言不閉合於差集和補集之下。

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

注意圖靈可識別語言和圖靈可判定語言的區別：若${\displaystyle S}$是圖靈可識別語言，則只需存在一台圖靈機${\displaystyle M}$，當${\displaystyle M}$的輸入${\displaystyle \omega \in S}$時，${\displaystyle M}$一定會停機並進入接受狀態；當${\displaystyle M}$的輸入${\displaystyle \omega \notin S}$時，${\displaystyle M}$可能停機並進入拒絕狀態，或者永不停機。而若${\displaystyle S}$是圖靈可判定語言，則必須存在圖靈機${\displaystyle M}$，使得對於任意輸入串${\displaystyle \omega \in \Sigma ^{*}}$，${\displaystyle M}$總能停機，並根據${\displaystyle \omega }$ 屬於或不屬於 ${\displaystyle S}$分別進入接受或拒絕狀態。

並不是所有的語言都是圖靈可識別的，可以證明存在圖靈不可識別語言。

定理

• 波斯特定理
• 克萊尼–波斯特定理
• 弗里德堡–穆奇尼克定理
• 波斯納–羅賓遜定理
• 跳躍逆轉定理

參見

• 圖靈機
• 枚舉器
• 遞歸語言
• 遞歸可枚舉集合