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

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

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

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

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

設(shè) S ? Σ* 是一個(gè)語(yǔ)言想暗，若存在圖靈機(jī)M使得 L(M)=S，則稱圖靈機(jī)M識(shí)別S杨箭，且S稱為圖靈可識(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)表示。通常我們假定這些方法必須滿足以下的要求：

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

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

3.基本上人可以僅用紙張和鉛筆來(lái)執(zhí)行滨彻。

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

此類方法的一個(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ǔ)言。