基本介紹
簡介,形式定義,兩個定義的等價性,圖靈可識別語言與圖靈可判定語言的關係,參見,
簡介
形式定義
遞歸可枚舉語言定義:設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分別進入接受或拒絕狀態。



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