基本介紹
簡介,形式定義,兩個定義的等價性,圖靈可識別語言與圖靈可判定語言的關係,參見,
簡介
形式定義
遞歸可枚舉語言定義：設S⊆ Σ為一個語言，E是一個枚舉器，若L（E） =S，則稱E枚舉了語言S。若存在這樣 的E，S就稱為遞歸可枚舉語言。
注意，枚舉器E可以以任意的順序枚舉語言L（E），而且L（E） 中的某個串可能會被E多次重複地列印。
圖靈可識別語言定義：設M是一台圖靈機，若在輸入串Ω上M運行後可進入接受狀態並停機，則稱M接受串Ω。M所接受的所有字元串的集合稱為M所識別的語言，簡稱M的語言，記作L(M)。
設
是一個語言，若存在圖靈機M使得L(M)=S，則稱圖靈機M識別S，且S稱為圖靈可識別語言。
兩個定義的等價性
下列定理揭示了遞歸可枚舉語言和圖靈可識別語言的聯繫。
定理：一個語言是圖靈可識別的，若且唯若它是遞歸可枚舉的。
證明：若有枚舉器E枚舉語言S，構造一個圖靈機M如下：
M= 對於輸入ω
- 運行E，依次生成字元串s1,s2, ...；
- 若遇到某個si= ω則進入接受狀態並停機。
注意當ω ∉S時，M可能永不停機，但M所接受的語 言集合恰好是S，所以M識別了S。
假設我們有圖靈機M識別語言S，構造一個枚舉器E如下：
E= 忽略輸入
- 對i= 1, 2, 3, ...重複下列步驟；
- 設Σ= {s1,s2, ...}，分別將s1,s2, ... ,si作為M的輸入，模擬M執行i步；
- 若某個sj, 1 ≤ j ≤ i，在i步內可被M接受，則將其輸出。
顯然，這樣構造的枚舉器E最終輸出的語言恰好就是S。注意S中的字元串並 沒有在E中按字典序輸出，而且同一個串可能會被E輸出多次，但根據枚舉器的定義，這些都是允許的。
圖靈可識別語言與圖靈可判定語言的關係
注意圖靈可識別語言和圖靈可判定語言的區別：若S是圖靈可識別語言，則只需存在一台圖靈機M，當M的輸入
時，M一定會停機並進入接受狀態；當M的輸入
時，M可能停機並進入拒絕狀態，或者永不停機。而若S是圖靈可判定語言，則必須存在圖靈機M，使得對於任意輸入串
，M總能停機，並根據Ω屬於或不屬於S分別進入接受或拒絕狀態。
並不是所有的語言都是圖靈可識別的，可以證明存在圖靈不可識別語言。
