形式語言課件：第5章 不可判定性

第5章不可判定性5.1Church-Turing論題5.2通用Turing機(jī)5.3停機(jī)問題5.4與Turing機(jī)有關(guān)的不可判定問題5.5與文法有關(guān)的不可解問題5.6不可解的鋪磚問題5.7遞歸語言的性質(zhì)第5章不可判定性5.1Church-Turing論題Church-Turing論題的描述

采用在所有輸入上停機(jī)的Turing機(jī)作為與“算法”的直覺化概念相對應(yīng)的精確的形式化概念。----可判定性機(jī)器是算法，半判定機(jī)器不是算法。不能被變換成在所有輸入上停機(jī)的Turing機(jī)的任何東西都不能被認(rèn)為是算法，而所有這樣的機(jī)器都被正確的稱為算法。5.2通用Turing機(jī)通用Turing機(jī)概念用Turing機(jī)的形式化這種編程語言寫的一段程序，它可以用來解釋執(zhí)行用同樣語言寫的另一段程序，這種用Turing機(jī)的形式化編程語言編寫的具有解釋執(zhí)行功能的程序叫做通用Turing機(jī)。---類似于自編譯系統(tǒng)Turing機(jī)的一般方法

Turing機(jī)的描述可用來作為其他Turing機(jī)的輸入。即要定義一個(gè)語言，它的字符串都是Turing機(jī)的合法表示。問題：無論我們?yōu)檫@種表示選擇多么大的字母表，總是存在有更多狀態(tài)和更多帶符號(hào)的Turing機(jī)。解決方法：把狀態(tài)和帶符號(hào)編碼成固定字母表上的字符串。具體方法：約定：表示Turing機(jī)狀態(tài)的字符串形如{q}{0，1}*，即字母q后面跟著二進(jìn)制字符串。同理，帶符號(hào)總是表示為{a}{0，1}*里的字符串。設(shè)M={K，∑，δ，s，H}是Turing機(jī)，設(shè)i和j是滿足2i≥|K|和2j≥|∑|+2的最小整數(shù)。于是，K里的每一個(gè)狀態(tài)都表示成q后面跟著長度為i的二進(jìn)制字符串，∑里的每個(gè)符號(hào)類似地表示成字母a后面跟著j位的二進(jìn)制字符串。

對特殊符號(hào)

?，?，←，→的表示，分別被固定成4個(gè)在字典順序下最小的符號(hào)：?總是表示成a0j，?表示成a0j-11，←表示成a0j-210，→表示成a0j-211。初始狀態(tài)總是表示成在字典序下的第一種狀態(tài)，即q0i。注意：在符號(hào)a和q后面跟著的字符串里，用前綴的0來保證總長度達(dá)到所要求的長度。

若把整臺(tái)Turing機(jī)M的表示記作“M”，則：“M”包括狀態(tài)轉(zhuǎn)移表δ，即它是形如（q，a，p，b）的字符串的序列，其中q和p表示狀態(tài)，a和b標(biāo)識(shí)符號(hào)。約定：從δ(s,?)開始，以字典序下的升序排列四元組。停機(jī)狀態(tài)集H將被直接確定，因?yàn)橥C(jī)狀態(tài)不出現(xiàn)在”M”的任何四元組的第一個(gè)分量上。若M判定語言，因此H={y,n}，則約定y是這兩種停機(jī)狀態(tài)中在字典序下較小的。通過這種方法，任意的Turing機(jī)都可被表示出來。并且可以用同樣的方法表示Turing機(jī)的字母表里的字符串(即輸入串)。例5.2.1考慮M=（K，∑，δ，s，{h}），其中K={s，q，h}，∑={?

，?，a}，并且δ如表5-1所示。

狀態(tài)符號(hào)δsas?s

?qaq?

q?（q,?

）（h,?

）（s,→）（s,a）（s,→）（q,→）表5-1狀態(tài)/符號(hào)表示sqh??←→aq00q01q11a000a001a010a011a100表5-2K={s，q，h}，∑={?，?，a}所以滿足2i≥3和2j≥3+2的最小整數(shù)為i=2和j=3因此，符號(hào)串?aa?a的表示是“?aa?a”=a001a100a100a000a100Turing機(jī)M的表示“M”是下列字符串：（狀態(tài)轉(zhuǎn)移描述）“M”=(q00,a100,q01,a000),(q00,a000,q11,a000),(q00,a001,q00,a011),(q01,a100,q00,a011),(q01,a000,q00,a011),(q01,a001,q01,a011)通用Turing機(jī)U，它用其他機(jī)器的編碼作為程序來指導(dǎo)它的操作。

U收到兩個(gè)自變量，分別是機(jī)器M的描述“M”和輸入字符串w的描述“w”。希望U具有的性質(zhì)：U在輸入“M”“w”上停機(jī)當(dāng)且僅當(dāng)M在輸入w上停機(jī)。U（“M”“w”）=M（w）用第4章開發(fā)的Turing機(jī)的函數(shù)記號(hào)表示為：通用Turing機(jī)實(shí)際上描述是密切相關(guān)的3帶機(jī)器U’（單帶機(jī)U將模擬U’）：第一條帶包含M當(dāng)前帶內(nèi)容的編碼W’；第二條帶包含M自身的編碼M’；第三條帶包含在被模擬的計(jì)算中M當(dāng)前的狀態(tài)的編碼。U’掃描第二條帶直到發(fā)現(xiàn)第一個(gè)分量與寫在第三條帶上的狀態(tài)編碼相匹配，第二分量與在第一條帶里掃描的符號(hào)編碼相匹配的四元組；----利用前兩個(gè)分量找到相應(yīng)的四元組若找到這樣的四元組，則U’把第三條帶上的狀態(tài)改成四元組的第三個(gè)分量，并且在第一條帶里完成四元組的第四個(gè)分量所提示的操作；若在第二條帶里找不到規(guī)定的狀態(tài)與符號(hào)的組合，則意味著第三條帶上的狀態(tài)是停機(jī)狀態(tài)。U’也在適當(dāng)?shù)臓顟B(tài)里停機(jī)。U’模擬M的過程：5.3停機(jī)問題halts(P,X)------P是一個(gè)程序，X輸入halts(P,X)是這樣一個(gè)程序：它收到用同樣語言寫的程序P和這個(gè)程序的輸入X作為輸入。它總是正確地判定在輸入X上程序P是否停機(jī)（若停機(jī)它返回“是”），或者P是否死循環(huán)（若P死循環(huán)它返回“否”）。這段程序命名為halts(P,X)。

這是最有價(jià)值的程序，你可用它完成許多不尋常的事情。比如你可用它寫用不祥的名字diagonal(X)命名的另一段程序(即判斷一個(gè)程序X對于它自己作為輸入時(shí)是否停機(jī))。

diagonal(X)定義如下：

diagonal(X)a:ifhalts(X,X)thengotoaelsehalt

如果你的halts程序斷定當(dāng)程序X用它自身X作為輸入時(shí)X停機(jī)，那么diagonal(X)死循環(huán)；否則它停機(jī)。

矛盾：diagonal(diagonal)是否停機(jī)？它停機(jī)當(dāng)且僅當(dāng)對halts(diagonal,diagonal)的調(diào)用返回“否”；即它停機(jī)當(dāng)且僅當(dāng)它不停機(jī)。結(jié)論：假設(shè)是假的，程序halts(P,X)其實(shí)并不存在。沒有程序，沒有算法可解決假設(shè)halts解決的問題：判別任意的程序是停機(jī)還是死循環(huán)。非遞歸的語言定義及其證明設(shè)H={“M””w”：Turing機(jī)M在輸入w上停機(jī)}注意：H是遞歸可枚舉的，它是通用Turing機(jī)半判定的語言。確實(shí)，在輸入“M”“w”上，恰好當(dāng)輸入屬于H時(shí)U才停機(jī)。若H是遞歸的，則每個(gè)遞歸可枚舉語言都是遞歸的。即：所有遞歸可枚舉語言也是Turing機(jī)可判定的(不是半判定)，當(dāng)且僅當(dāng)H是遞歸的。------通過對角化可知假設(shè)導(dǎo)致邏輯矛盾。定理5.3.1語言H不是遞歸的;所以，遞歸語言類是遞歸可枚舉語言類的真子集。

注：遞歸語言是可判定的，而H是不可判定的。定理5.3.2

遞歸可枚舉語言類在補(bǔ)運(yùn)算下不封閉。

注：反證法。假設(shè)在補(bǔ)運(yùn)算下封閉（即補(bǔ)語言也是遞歸可枚舉語言），則H就是可判定的。茅盾！5.4與Turing機(jī)有關(guān)的不可判定問題不可判定：沒有對任意給定的Turing機(jī)M和輸入字符串ω判定M是否接受ω的算法。沒有算法的問題稱為不可判定的或者不可解的。最有名的和最基本的不可判定問題是辨別給定的Turing機(jī)在給定的輸入上是否停機(jī)的問題，我們剛剛證明它的不可判定性。這個(gè)問題通常稱為Turing機(jī)的停機(jī)問題。定義5.4.1設(shè)L1,L2

∑*是兩個(gè)語言。從L1到L2的規(guī)約是遞歸函數(shù)φ:∑*→∑*使得x∈L1當(dāng)且僅當(dāng)φ(x)∈L2定理5.4.1

若L1不是遞歸的，并且存在從L1到L2的歸約，則L2也不是遞歸的。

證明：假設(shè)L2是遞歸的，比如說用Turing機(jī)M2判定，并設(shè)T是計(jì)算歸約φ的Turing機(jī)。那么Turing機(jī)TM2判定L1。但是L1是不可判定的，矛盾。通過對角化證明了停機(jī)問題是不可判定的，就可由此得出一大批問題的不可判定性。這里可直接通過歸約證明：定理5.4.2

與Turing機(jī)有關(guān)的下列幾個(gè)問題是不可判定的。a)給定Turing機(jī)M和輸入字符串ω，M是否在輸入ω上停機(jī)？b)給定Turing機(jī)M，M是否在空帶上停機(jī)？c)給定Turing機(jī)M，究竟有沒有M在上面停機(jī)的字符串？d)給定Turing機(jī)M，M是否在每一個(gè)輸入字符串上都停機(jī)？e)給定兩臺(tái)Turing機(jī)M1和M2，他們是否在同樣的字符串上停機(jī)？f)給定Turing機(jī)M，M半判定的語言是否正則？是否上下文無關(guān)？是否遞歸？g)另外，存在某臺(tái)固定機(jī)M0，對下列問題是否不可判定：給定ω，M0是否在ω上停機(jī)？證明：可以把停機(jī)問題歸約到該問題或把前一個(gè)問題歸約到后者。見書上166-167頁5.5與文法有關(guān)的不可解問題不可解問題不但出現(xiàn)在Turing機(jī)的領(lǐng)域里，而且事實(shí)上出現(xiàn)在所有的數(shù)學(xué)領(lǐng)域里。例如存在多個(gè)與文法有關(guān)的不可判定問題，總結(jié)如下：定理5.5.1

下列每個(gè)問題都是不可判定的：a)對給定的文法G和字符串ω，判定是否ω∈L(G)。b)對給定的文法G，判定是否e∈L(G)。c)對兩個(gè)給定的文法G1和G2，判定是否L(G1)＝L(G2)。d)對任意的文法G，判定是否L(G)＝Φe)另外，存在某個(gè)固定的文法G0，使得判定任意給定的字符串ω是否屬于L(G0)，這是不可判定的。定理5.5.2

下列每個(gè)問題都是不可判定的：a)給定上下文無關(guān)文法G，是否L(G)＝∑*?b)給定兩個(gè)上下無關(guān)文法G1和G2，是否L(G1)＝L(G2)？c)給定兩臺(tái)下推自動(dòng)機(jī)M1和M2，它們是否恰好接受同樣的語言？d)給定下推自動(dòng)機(jī)M，是否能找出狀態(tài)數(shù)量最少的等價(jià)的下推自動(dòng)機(jī)。5.6不可解的鋪磚問題問題描述：給定磚的有窮集，每塊磚是單位正方形，而且我們有每塊磚的無窮多塊復(fù)制品。要求我們用這些磚的復(fù)制品來鋪滿平面的第一象限。僅有的限制是左下角放特殊的磚，只有特定的成對的磚才可彼此水平相鄰,只有特定的成對的磚才可彼此垂直的相鄰。（磚不可被旋轉(zhuǎn)或翻面）給定磚的有窮集，原點(diǎn)磚和相鄰規(guī)則，有沒有判定第一象限能否被鋪滿的算法？這個(gè)問題可形式化如下。鋪磚系統(tǒng)是四元組⊙=(D,d0,H,V)，其中D是磚的有窮集，d0∈D，并且H,V?D×D。根據(jù)⊙的鋪磚是函數(shù)f:N×ND使得下列關(guān)系成立：

f(0,0)=d0(f(m,n),f(m+1,n))∈H對于所有的m,n∈N

(f(m,n),f(m,n+1))∈V對于所有的m,n∈N定理5.6.1：給定鋪磚系統(tǒng)，判定是否存在根據(jù)這個(gè)系統(tǒng)的鋪磚，這個(gè)問題是不可判定的。

證明：主要思想是把給定Turing機(jī)M，判定M是否在輸入e上不停機(jī)的問題（停機(jī)問題的補(bǔ)，所以是不可判定問題）歸約到鋪磚問題上。-----略5.7遞歸語言的性質(zhì)定理5.7.1:語言是遞歸