遞歸可枚舉(Recursively Enumerable)語(yǔ)言

與 圖靈可識(shí)別(Recognizable)語(yǔ)言 的形式定義

遞歸可枚舉語(yǔ)言定義：設(shè)S ? Σ*為一個(gè)語(yǔ)言，E是一個(gè)枚舉器，若L（E） = S，則稱(chēng)E 枚舉了語(yǔ)言S。若存在這樣 的E，S就稱(chēng)為遞歸可枚舉語(yǔ)言。

注意，枚舉器E可以以任意的順序枚舉語(yǔ)言L(fǎng)（E），而且L（E） 中的某個(gè)串可能會(huì)被E多次重復(fù)地打印。

圖靈可識(shí)別語(yǔ)言定義：設(shè) M是一臺(tái)圖靈機(jī)，若在輸入串ω上M運(yùn)行后可進(jìn)入接受狀態(tài)并停機(jī)，則稱(chēng)M接受串ω。M所接受的所有字符串的集合稱(chēng)為M所識(shí)別的語(yǔ)言，簡(jiǎn)稱(chēng) M的語(yǔ)言，記作L(M)。

設(shè) S ? Σ* 是一個(gè)語(yǔ)言，若存在圖靈機(jī)M使得 L(M)=S，則稱(chēng)圖靈機(jī)M識(shí)別S，且S稱(chēng)為圖靈可識(shí)別語(yǔ)言。

兩個(gè)定義的等價(jià)性

下列定理揭示了遞歸可枚舉語(yǔ)言和圖靈可識(shí)別語(yǔ)言的聯(lián)系。

定理：一個(gè)語(yǔ)言是圖靈可識(shí)別的，當(dāng)且僅當(dāng)它是遞歸可枚舉的。

證明：若有枚舉器E枚舉語(yǔ)言S，構(gòu)造一個(gè)圖靈機(jī)M如下：

M = 對(duì)于輸入ω

運(yùn)行E，依次生成字符串s1, s2, ...；

若遇到某個(gè)si = ω則進(jìn)入接受狀態(tài)并停機(jī)。

注意當(dāng)ω ? S時(shí)，M可能永不停機(jī)，但M所接受的語(yǔ) 言集合恰好是S，所以M識(shí)別了S。

假設(shè)我們有圖靈機(jī)M識(shí)別語(yǔ)言S，構(gòu)造一個(gè)枚舉器E如下：

E = 忽略輸入

對(duì)i = 1, 2, 3, ...重復(fù)下列步驟；

設(shè)Σ* = {s1, s2, ...}，分別將s1, s2, ... ,si作為M的輸入，模擬M執(zhí)行i步；

若某個(gè)sj, 1 ≤ j ≤ i，在i步內(nèi)可被M接受，則將其輸出。

顯然，這樣構(gòu)造的枚舉器E最終輸出的語(yǔ)言恰好就是S。注意S中的字符串并 沒(méi)有在E中按字典序輸出，而且同一個(gè)串可能會(huì)被E輸出多次，但根據(jù)枚舉器的定義，這些都是允許的。

圖靈可識(shí)別(Recognizable)語(yǔ)言

與 圖靈可判定(Decidable)語(yǔ)言 的關(guān)系

注意圖靈可識(shí)別語(yǔ)言和圖靈可判定語(yǔ)言的區(qū)別：若S是圖靈可識(shí)別語(yǔ)言，則只需存在一臺(tái)圖靈機(jī)M，當(dāng) M的輸入ω ∈ S時(shí)，M一定會(huì)停機(jī)并進(jìn)入接受狀態(tài)；當(dāng)M的輸入ω ? S時(shí)，M可能停機(jī)并進(jìn)入拒絕狀態(tài)，或者永不停機(jī)。

而若S是圖靈可判定語(yǔ)言，既遞歸(Recursive)語(yǔ)言，則必須存在圖靈機(jī)M，使得對(duì)于任意輸入串ω ? Σ*，M總能停機(jī)，并根據(jù)ω屬于或不屬于S分別進(jìn)入接受或拒絕狀態(tài)。

并不是所有的語(yǔ)言都是圖靈可識(shí)別的，可以證明存在圖靈不可識(shí)別語(yǔ)言。

停機(jī)問(wèn)題

停機(jī)問(wèn)題就是判斷任意一個(gè)程序是否會(huì)在有限的時(shí)間之內(nèi)結(jié)束運(yùn)行的問(wèn)題。

該問(wèn)題等價(jià)于如下的判定問(wèn)題：給定一個(gè)程序P和輸入w，程序P在輸入w下是否能夠最終停止（而不是進(jìn)入無(wú)限循環(huán)）。

用數(shù)學(xué)語(yǔ)言描述，則其本質(zhì)問(wèn)題為: 給定一個(gè)圖靈機(jī)T，和一個(gè)任意語(yǔ)言集合S，是否T會(huì)最終停機(jī)于每一個(gè)ω ∈ S。其意義相同于可確定語(yǔ)言。顯然任意有限 S 是可判定性的，可數(shù)的（countable）S 也是可停機(jī)的。

艾倫·圖靈在1936年用對(duì)角論證法證明了，不存在解決停機(jī)問(wèn)題的通用算法。

邱奇-圖靈(Church-Turing)論題

邱奇-圖靈論題認(rèn)為“任何在算法上可計(jì)算的問(wèn)題同樣可由圖靈機(jī)計(jì)算”

另外一種說(shuō)法就是邏輯和數(shù)學(xué)中的有效或機(jī)械方法可由圖靈機(jī)來(lái)表示。通常我們假定這些方法必須滿(mǎn)足以下的要求：

1.一個(gè)方法由有限多簡(jiǎn)單和精確的指令組成，這些指令可由有限多的符號(hào)來(lái)描述。

2.該方法總會(huì)在有限的步驟內(nèi)產(chǎn)生出一個(gè)結(jié)果。

3.基本上人可以?xún)H用紙張和鉛筆來(lái)執(zhí)行。

4.該方法的執(zhí)行不需人類(lèi)的智慧來(lái)理解和執(zhí)行這些指令。

此類(lèi)方法的一個(gè)范例便是用歐幾里得輾轉(zhuǎn)相除法確定兩個(gè)自然數(shù)的最大公約數(shù)。

例題

設(shè)當(dāng)前有遞歸語(yǔ)言 L，其可接納的字符串集為 Σ。求證：L的補(bǔ)集：Σ*\L 也為遞歸語(yǔ)言。

證明過(guò)程：

因?yàn)長(zhǎng)是遞歸語(yǔ)言，則存在一臺(tái)圖靈機(jī)M1，能夠完成：

1.當(dāng)且僅當(dāng)ω ∈ Σ*且 ω ∈ L 時(shí)，接受輸入串ω并總能進(jìn)入停機(jī)狀態(tài)，該停機(jī)狀態(tài)為最終態(tài)。

2.當(dāng)且僅當(dāng)ω ∈ Σ* 且 ω ? L 時(shí)，拒絕輸入串ω并總能進(jìn)入停機(jī)狀態(tài)，該停機(jī)狀態(tài)為非最終態(tài)。

現(xiàn)在通過(guò)將M1的最終態(tài)與非最終態(tài)互換（原本的非最終態(tài)變?yōu)樽罱K態(tài)，最終態(tài)變?yōu)榉亲罱K態(tài)），構(gòu)造另一臺(tái)圖靈機(jī)M2。則M2能夠完成：

1.當(dāng)且僅當(dāng)ω ∈ Σ*且 ω ∈ Σ*\L 時(shí)，接受輸入串ω并總能進(jìn)入停機(jī)狀態(tài)，該停機(jī)狀態(tài)為最終態(tài)。

2.當(dāng)且僅當(dāng)ω ∈ Σ* 且 ω ? Σ*\L 時(shí)，拒絕輸入串ω并總能進(jìn)入停機(jī)狀態(tài)，該停機(jī)狀態(tài)為非最終態(tài)。

故M1拒絕的輸入將被M2接受，M1接受的輸入將被M2拒絕。

則M2恰好接受 Σ*\L ， 即 Σ*\L 也為遞歸語(yǔ)言。