形式語言與自動(dòng)機(jī)課件

計(jì)算理論第5章可歸約性1計(jì)算理論第5章可歸約性1前言

在第4章已經(jīng)確定采用圖靈機(jī)作為通用計(jì)算器機(jī)的模型，并介紹了幾個(gè)在圖靈機(jī)上可解的問題，還給出了一個(gè)計(jì)算機(jī)不可解的問題，即ATM。本章討論另外幾個(gè)不可解的問題。在討論過程中，將介紹一個(gè)基本方法，可用來證明問題是計(jì)算上不可解的，這個(gè)方法稱為可歸約性。

歸約旨在將一個(gè)問題轉(zhuǎn)化為另一個(gè)問題，且使得可以用第二個(gè)問題的解來解第一個(gè)問題，在日常生活中，雖然不這樣稱呼，但時(shí)常會(huì)遇見可歸約性問題。

2前言在第4章已經(jīng)確定采用圖靈機(jī)作為通用計(jì)算器機(jī)前言例如，在一個(gè)新城市中認(rèn)路，如果有一張地圖，事情就容易了。這樣，就將在城市認(rèn)路問題歸約為得到地圖問題?？蓺w約性總是涉及兩個(gè)問題，稱之為A和B。如果A可歸約到B，就可用B的解來解A。在上述例子中，A是城市認(rèn)路問題，B是得到地圖問題。注意，可歸約性說的不是怎樣去解A或B，而是在知道B的解時(shí)怎么去解A。3前言例如，在一個(gè)新城市中認(rèn)路，如果有一張地圖，事情就容易了。主要內(nèi)容5.1語言理論中的不可判定問題5.2一個(gè)簡(jiǎn)單的不可判定問題5.3映射可歸約性

5.3.1可計(jì)算函數(shù) 5.3.2映射可歸約性的形式定義

4主要內(nèi)容5.1語言理論中的不可判定問題4語言理論中的不可判定問題ATM是不可判定的，即確定個(gè)圖靈機(jī)是否接受一個(gè)給定的輸入問題是不可判定的。下面考慮一個(gè)與之相關(guān)的問題：HALTTM，即確定一個(gè)圖靈機(jī)對(duì)給定輸入是否停機(jī)（通過接受或拒絕）問題。若將ATM歸約到HALTTM，就可以利用ATM的不可判定性證明HALTTM的不可判定性。設(shè):

HALTTM={<M,w>|M是一個(gè)TM,且對(duì)輸入w停機(jī)}5語言理論中的不可判定問題ATM是不可判定的，即確定個(gè)圖靈機(jī)是語言理論中的不可判定問題定理5.1HALTTM是不可判定的。

為得到矛盾，假設(shè)TMR判定HALTTM，由之可以構(gòu)造TMS來判定ATM,其構(gòu)造如下：S=“在輸入<M，w>上，此處<M，w>是TMM和串w的編碼：1)在輸入<M，w>上運(yùn)行TMR。2)如果R拒絕，則拒絕。3)如果R接受，則在w上模擬M，直到它停機(jī)。4)如果M已經(jīng)接受，則接受；如果M已經(jīng)拒絕，則拒絕。顯然，如果R判定HALTTM，則S判定ATM。因?yàn)锳TM是不可判定的，故HALTTM也必定是不可判定的。反證法，假設(shè)可判定，證明ATM是可判定的。6語言理論中的不可判定問題定理HALTTM是不可判定的。為得語言理論中的不可判定問題定理5.2ETM是不可判定的。

先用標(biāo)準(zhǔn)術(shù)語來寫在證明思路中描述的那上修改型機(jī)器M1.M1=“在輸入x上：1)如果x≠w，則拒絕。2)如果x=w，則在x上運(yùn)行M，當(dāng)M接受時(shí)，就接受。”這個(gè)機(jī)器以w作為它的描述的一部分。檢查x=w是否成立的方法很顯然，即掃描輸入并用一個(gè)字符一個(gè)字符地將它與w進(jìn)行比較，就可確定它們是否相同。

反證法，假設(shè)可判定，證明ATM是可判定的。除w外M1拒絕所有串7語言理論中的不可判定問題定理ETM是不可判定的。語言理論中的不可判定問題再假設(shè)TMR判定ETM。如下構(gòu)造判定ATM的TMS:S=“在輸入<M，w>上，此處<M，w>是TMM和串w的編碼：1)用M和w的描述來構(gòu)造上述TMM1。2)在輸入<M1>上運(yùn)行R。3)如果R接受，則拒絕；如果R拒絕，則接受?！辈豢?，M接受w說明L(M1)是空集，因此M1不接受w8語言理論中的不可判定問題再假設(shè)TMR判定ETM。如下構(gòu)造判語言理論中的不可判定問題另一個(gè)與圖靈機(jī)有關(guān)的計(jì)算問題也很有意思，該問題是：給定一個(gè)圖靈機(jī)和一個(gè)可由某個(gè)更簡(jiǎn)單的計(jì)算模型識(shí)別的語言，測(cè)定此圖靈機(jī)是否識(shí)別此語言。例如：令REGULARTM是測(cè)定一個(gè)給定的圖機(jī)是否有一個(gè)與之等價(jià)的有窮自動(dòng)機(jī)問題，則這個(gè)問題與測(cè)定一個(gè)給定的圖靈機(jī)是否識(shí)別一個(gè)與此正則語言的問題相同。設(shè)：

REGULARTM={<M>|M是一個(gè)TM，且L(M)是一個(gè)正則語言}9語言理論中的不可判定問題另一個(gè)與圖靈機(jī)有關(guān)的計(jì)算問題也很有意語言理論中的不可判定問題定理5.3

REGULARTM是不可判定的。設(shè)R是判定REGULARTM的一個(gè)TM，下面構(gòu)造判定ATM的TMS。S的運(yùn)行方式如下：S=“對(duì)于輸入<M，w>，其中M是TM，w是串：1)構(gòu)造下述TMM2：M2=“在輸入x上：a)如果x具有形式0n1n，則接受。b)如果x不具有此形式，則在輸入w上運(yùn)行M。如果M接受w，則接受?！?)在輸入<M2>上運(yùn)行R。3)如果R接受，則接受；如果R拒絕，則拒絕?！?0語言理論中的不可判定問題定理REGULARTM是不可判定的語言理論中的不可判定問題定理5.4EQTM是不可判定的。

設(shè)TMR判定EQTM。如下構(gòu)造判定ETM的TMS：S=“對(duì)于輸入<M>，其中M是TM：1)在輸入<M，M1>上運(yùn)行R，其中M1是拒絕所有輸入的圖靈機(jī)。2)如果R接受，則接受；如果R拒絕，則拒絕。如果R判定EQTM，則S判定ETM。但由定理5.2，ETM是不可判定的，故EQTM也是不可判定的。11語言理論中的不可判定問題定理EQTM是不可判定的。設(shè)TM語言理論中的不可判定問題定義5.5

設(shè)M是一個(gè)圖靈機(jī)，w是一個(gè)串。M在w上的一個(gè)

接受計(jì)算歷史是一個(gè)格局序列C1，C2，．．．,Cl，其中C1是M在w上的起始格局，Cl是M的一個(gè)接受格局，且每個(gè)Ci都是Ci-1的合法結(jié)果，即符合M的規(guī)則。M在w上的一拒絕計(jì)算歷史可類似定義，只是Cl應(yīng)是一個(gè)拒絕格局。12語言理論中的不可判定問題定義設(shè)M是一個(gè)圖靈機(jī)，定義5.6

線性界限自動(dòng)機(jī)是一種受到限制的圖靈機(jī)，它不允許其讀寫頭離開包含輸入的帶區(qū)域。如果此機(jī)器試圖將它的讀寫頭移出輸入的兩個(gè)端點(diǎn)，則讀寫頭就保持在原地不動(dòng)。這與普通圖靈機(jī)的讀寫頭不會(huì)離開帶子的左端點(diǎn)的方式一樣。語言理論中的不可判定問題定義5.6ababa控制器13定義線性界限自動(dòng)機(jī)是一種受到限制的圖靈機(jī)，它不允語言理論中定義5.6設(shè)M是有q個(gè)狀態(tài)和g個(gè)帶符號(hào)的LBA。對(duì)于長(zhǎng)度為n的帶子，M恰有qngn個(gè)不同的格局。語言理論中的不可判定問題引理5.7

M的格局就像計(jì)算中間的一快照。格局由控制狀態(tài)、讀寫頭位置和帶內(nèi)容組成。這里，M有q個(gè)狀態(tài)。它的帶長(zhǎng)度是n，所以讀寫頭可能處于n個(gè)位置之一，且gn多個(gè)帶符號(hào)串可能出現(xiàn)在帶上。此三個(gè)量的乘積就是帶長(zhǎng)為n的M的格局總數(shù)。

14定義設(shè)M是有q個(gè)狀態(tài)和g個(gè)帶符號(hào)的LBA。對(duì)于長(zhǎng)度為語言理定義5.6ALBA是可判定的。

語言理論中的不可判定問題定理5.8證明判定ALBA的算法如下：L=“對(duì)于輸入<M，w>，其中M是LBA，w是串：1)在w上模擬Mqngn步，或者直到它停機(jī)。2)如果M停機(jī)，則當(dāng)它接受時(shí)接受，拒絕時(shí)拒絕。如果它還沒有停機(jī)，就拒絕?！比绻鸐在w上運(yùn)行qngn步還沒有停機(jī)，根據(jù)引理5.7，它必定在重復(fù)某個(gè)格局，即陷入了循環(huán)。這就是算法為什么在此情形下拒絕的原因。15定義ALBA是可判定的。語言理論中的不可判定問題定理證明定義5.6

ELBA是不可判定的。

語言理論中的不可判定問題定理5.9現(xiàn)在構(gòu)造從ATM到ELBA的歸約。假設(shè)TMR判定ELBA。如下構(gòu)造判定ATM的TMS：S=“對(duì)于輸入<M，w>，其中M是TM，w是串：1)如在證明思路中所描述的那樣從M和w構(gòu)造LBAB。2)在輸入<B>上運(yùn)行R。3)如果R拒絕，則接受；如果R接受，則拒絕?！?/p>

####…##C1C2C3Cl16定義ELBA是不可判定的。語言理論中的不可判定問題定理如果R接受<B>，則L(B)=。這樣，M在w上就沒接受計(jì)算歷史，M也就不接受w.因此，S也就拒絕<M，w>。類似地，如果R拒絕<B>，則B的語言不空。B能夠接受的唯一串是M在w上的接受計(jì)算歷史。這樣，M必定接受w。相應(yīng)地，S也就接受<M，w>。下圖是檢查這樣一個(gè)TM計(jì)算歷史的示意圖。

語言理論中的不可判定問題q3ab#xxq5b#……#xBCiCi+117如果R接受<B>，則L(B)=。這樣，M在w上就沒接使用利用計(jì)算歷史的歸約技術(shù)，還能建立有關(guān)上下文無關(guān)文法和下推自動(dòng)機(jī)問題的不可判定性。加快一下，定理4.7介紹了一個(gè)算法來判定一個(gè)上下文無關(guān)文法是否派生串，即判定L(G)=是否成立。與此相關(guān)，現(xiàn)在要證明問題“測(cè)定一個(gè)上下文無關(guān)文法是否派生所有可能的串”是不可判定的。證明這個(gè)問題不可判定是證明上下文無關(guān)文法等價(jià)性問題不可判定的重要步驟。設(shè):ALLCFG={<G>|G是一個(gè)CFG且L(G)=*}語言理論中的不可判定問題18使用利用計(jì)算歷史的歸約技術(shù)，還能建立有關(guān)上下文無關(guān)文語言理論定義5.6ALLCFG是不可判定的。

語言理論中的不可判定問題定理5.10用反證法。為得到矛盾，假設(shè)ALLCFG是可判定的，用這個(gè)假設(shè)來證明ATM是可判定的。其證明與定理5.9的證明類似，只是稍微復(fù)雜一些，繞了一點(diǎn)點(diǎn)彎。這是一個(gè)從ATM出發(fā)利用計(jì)算歷史的歸約。但由于技術(shù)上的原因，對(duì)計(jì)算歷史的表示做了些修改，后面將解釋這樣做的原因。現(xiàn)在來描述怎樣運(yùn)用ALLCFG的判定過程來判定ATM。對(duì)于TMM和輸入串w，首先構(gòu)造一個(gè)CFGG，使得它派生所有串當(dāng)且僅當(dāng)M不接受w。所以，如果M接受w，則存在一個(gè)特別的串，G不派生它。這個(gè)串應(yīng)該是M在w上的計(jì)算歷史。即：設(shè)計(jì)G，使之派生所有不是M在w上接受計(jì)算歷史的串。

19定義ALLCFG是不可判定的。語言理論中的不可判定問題定語言理論中的不可判定問題為了使得CFGG派生所有不是M在w上接受計(jì)算歷史的串，采用下的策略。一個(gè)串不能成為M在w上的接受計(jì)算歷史的原因可能有多個(gè)。將M在w上的接受計(jì)算歷史表示成#C1#C2#...#Cl#，其中Ci是M在w上計(jì)算的第i步的格局。然后G派生出滿足下述條件的所有串：1)不以Cl開始。2)不以一個(gè)接受格局結(jié)束3)在M的規(guī)則下，某個(gè)Ci不恰好派生Ci+1。如果M不接受w，就沒有接受計(jì)算歷史存在，故所有串都因?yàn)檫@樣或那樣的問題而不能成為接受計(jì)算歷史，因此G將派生所有串，這正是所希望的。20語言理論中的不可判定問題為了使得CFGG派生所有不是M在w語言理論中的不可判定問題這個(gè)思路存在的問題是：當(dāng)D將Ci彈出棧時(shí)，它處于相反的左右為難，因而不適合與Ci+1比較。前面提到的繞彎就在此處。換一種方法來寫接受計(jì)算歷史，使得每隔一個(gè)格局就以相反的順序出現(xiàn)。奇數(shù)位置保持以向前的順序?qū)?，但偶?shù)位置向后寫。這種形式的一個(gè)接受計(jì)算歷史如下圖所示：

####…##C1C2RC3C4R#Cl21語言理論中的不可判定問題這個(gè)思路存在的問題是：當(dāng)D將Ci彈出主要內(nèi)容5.1語言理論中的不可判定問題5.2一個(gè)簡(jiǎn)單的不可判定問題5.3映射可歸約性

5.3.1可計(jì)算函數(shù) 5.3.2映射可歸約性的形式定義

22主要內(nèi)容5.1語言理論中的不可判定問題22本節(jié)將證明：不可判定性現(xiàn)象不僅能僅能局限于有限自動(dòng)機(jī)的問題，我們將給出一個(gè)關(guān)于串操作的不可判定問題，稱為波斯特對(duì)應(yīng)問題。可以很容易地將這個(gè)問題描述成一種游戲，多米諾骨牌。每個(gè)骨牌由兩個(gè)串構(gòu)成，一邊一個(gè)，單個(gè)骨牌看上去像一簇骨牌看起來像任務(wù)是將這些骨牌進(jìn)行排列(允許重復(fù))，使得在總計(jì)頂部符號(hào)后得到的串與總計(jì)詢問符號(hào)后得到的串相同。這樣的排列稱為一個(gè)匹配。例如，下面的排列就是這個(gè)游戲的一個(gè)匹配。一個(gè)簡(jiǎn)單的不可判定問題aabbcaaabcaaabcc,,,23本節(jié)將證明：不可判定性現(xiàn)象不僅能僅能局限于有限自動(dòng)機(jī)的問題，一個(gè)簡(jiǎn)單的不可判定問題aabbcacaaaababcc閱讀頂部后得到的串a(chǎn)bcaaabc，與總計(jì)詢問后得到的本同?？梢詫⒐桥谱冃问沟煤驮儐枌?duì)應(yīng)符號(hào)整齊地排列，以此更容易表示匹配。aabbccaaaaaabbcc24一個(gè)簡(jiǎn)單的不可判定問題aabbcacaaaababcc閱讀頂一個(gè)簡(jiǎn)單的不可判定問題

對(duì)某些骨牌簇，不可能找到這樣的匹配。例如，簇

不可能包含匹配，因?yàn)轫敳康拿總€(gè)串都比詢問對(duì)應(yīng)的串長(zhǎng)。波斯特對(duì)應(yīng)問題是：確定一簇骨牌是否有一個(gè)匹配。這個(gè)問題在算法上是不可解的。

abcabcacaccba,,25一個(gè)簡(jiǎn)單的不可判定問題對(duì)某些骨牌簇，不可能找到一個(gè)簡(jiǎn)單的不可判定問題在形式描述這個(gè)問題和給出它的證明之前，先來精確地描述這個(gè)問題，然后表示成一個(gè)。骨牌簇P是pcp的一個(gè)實(shí)例：

匹配是一個(gè)序列i1，i2，．．．，il，使ti1ti2．．．til=bi1bi2bil.問題是確定P是否有匹配。令PCP={<G>|P是波斯特對(duì)應(yīng)問題的一個(gè)實(shí)例，且P有匹配}

t1b1t2b2tkbk,,P=,…26一個(gè)簡(jiǎn)單的不可判定問題在形式描述這個(gè)問題和給出它的證定義5.6

PCP是不可判定的。

一個(gè)簡(jiǎn)單的不可判定問題定理5.11假設(shè)TMR判定PCP。構(gòu)造S來判定ATM。令M=(Q,,,,q0,qaccept,qreject)其中Q,,,分別是M的狀態(tài)集、輸入字母表、帶字母表和轉(zhuǎn)移函數(shù)。S構(gòu)造PCP的一個(gè)實(shí)例P，使得P有一個(gè)匹配當(dāng)且僅當(dāng)M接受w。為此，S首先構(gòu)造MPCP的一個(gè)實(shí)例P’。下面以七個(gè)部分來描述這個(gè)構(gòu)造。每個(gè)部分完成在w上模擬M的一個(gè)特定方面。在構(gòu)造過程中，為了解釋我們正在做什么，用一個(gè)例子插在構(gòu)造中。27定義PCP是不可判定的。一個(gè)簡(jiǎn)單的不可判定問題定理假設(shè)T一個(gè)簡(jiǎn)單的不可判定問題

第1部分：構(gòu)造以下方式開始：

將放入p’作為第一張骨牌

因?yàn)镻’是MPCP的一個(gè)實(shí)例，故匹配必須以這張骨牌開始。底部串以M在w上接受計(jì)算歷史中的第一個(gè)格局C1=q0w1w2．．．wn開始。如圖所示:##q0w1w2…wn#t1b1##…q0w1w2wn#28一個(gè)簡(jiǎn)單的不可判定問題第1部分：構(gòu)造以下方式開始：一個(gè)簡(jiǎn)單的不可判定問題

到目前為止，只得到一個(gè)部分匹配，其詢問串由C1=

＃q0w1w2．．．wn＃構(gòu)成，頂部串只有#。為獲得匹配，盤面擴(kuò)展串來匹配詢問串。用新骨牌來作這樣的擴(kuò)展。這些新的骨牌強(qiáng)迫模擬M的一次單步運(yùn)行，使得M的一下個(gè)格局出現(xiàn)在詢問串的擴(kuò)展中。第2、3、4部分在P’中增加的骨牌在模擬中起主要作用。第2部分處理讀寫向右運(yùn)動(dòng)，第3部分處理讀寫頭向左運(yùn)動(dòng)，第4部分處理不與讀寫關(guān)相鄰的帶方格。29一個(gè)簡(jiǎn)單的不可判定問題到目前為止，只得到一個(gè)部分匹配一個(gè)簡(jiǎn)單的不可判定問題第2部分：對(duì)于第一個(gè)a,b∈和q,r∈Q，其中q≠qreject，如果(q,a)=(r,b,R),則將放入P’中。第3部分：對(duì)于第一個(gè)a,b,c∈和q,r∈Q，其中q≠qreject，如果(q,a)=(r,b,L)，則將放入p’中。第4部分：對(duì)于每一個(gè)a∈，將放入p’中。這樣，第2、3和4部分的骨牌，使得我們能夠通過“在第一個(gè)格局之后增加第二個(gè)格局”的方法來擴(kuò)展匹配。希望這個(gè)過程能夠繼續(xù)下去，即增加第三個(gè)格局，然后第四個(gè)格局，等等。為此，需要增加一個(gè)新的骨牌來復(fù)制符號(hào)#。qabrcqarcbaa30一個(gè)簡(jiǎn)單的不可判定問題第2部分：對(duì)于第一個(gè)a,b∈和q,一個(gè)簡(jiǎn)單的不可判定問題第5部分：將和放入P’中接著上面的例子。假設(shè)在狀態(tài)q7且讀1時(shí)，M進(jìn)入狀q5，在帶上寫下0，并將讀寫頭向右移到。即(q7,1)=(q5,0,R)。則在P’中有骨牌最后的那個(gè)匹配被擴(kuò)展到#_###q710q520q500#q7##22q7110000##…31一個(gè)簡(jiǎn)單的不可判定問題第5部分：將一個(gè)簡(jiǎn)單的不可判定問題再假設(shè)在狀態(tài)q5且讀0時(shí)，M進(jìn)入狀態(tài)q9，在帶上寫下2，并將它的讀寫頭向左移動(dòng)。故(q5,1)=(q9,2,L)。則有骨牌第一個(gè)骨牌與本構(gòu)造部分有關(guān)，因?yàn)樽x寫頭左邊的符號(hào)是0。前面的部分匹配就被擴(kuò)展成

0q50q9021q50q9122q50q922_q50q9_2,,和2q9020#0##220q5q50000##…32一個(gè)簡(jiǎn)單的不可判定問題再假設(shè)在狀態(tài)q5且讀0時(shí)，M進(jìn)入狀態(tài)q一個(gè)簡(jiǎn)單的不可判定問題注意，構(gòu)造匹配就是在w上模擬M，這個(gè)過程要一直進(jìn)行到M到達(dá)停機(jī)狀態(tài)。如果出現(xiàn)了接受狀態(tài)，希望這個(gè)部分匹配的頂部“趕上”底部，從而使得這個(gè)匹配得以完成。為此，再增加加下骨牌。第6部分：對(duì)于第一個(gè)a∈，將和放入P’中這個(gè)步驟的效果是：在圖靈機(jī)停機(jī)后增加一些“偽步驟”。這里，讀寫頭“吃掉”一些鄰近的符號(hào)直到?jīng)]有符號(hào)剩下。再繼續(xù)前面的例子，假設(shè)到機(jī)器以接受狀態(tài)停機(jī)的地方為止的部分匹配是aqacceptqacceptqacceptaqaccept33一個(gè)簡(jiǎn)單的不可判定問題注意，構(gòu)造匹配就是在w上模擬M，這個(gè)過一個(gè)簡(jiǎn)單的不可判定問題剛才增加的骨牌允許匹配如下繼續(xù)進(jìn)行：##…21qaccept2#021qaccept2###2211qacceptqaccept0022##…#……#qaccept#34一個(gè)簡(jiǎn)單的不可判定問題剛才增加的骨牌允許匹配如下繼續(xù)進(jìn)行：#一個(gè)簡(jiǎn)單的不可判定問題第7部分：最的增加如下骨牌來完成匹配：##q0w1w2…wn####qacceptqaccept…###35一個(gè)簡(jiǎn)單的不可判定問題第7部分：最的增加如下骨牌一個(gè)簡(jiǎn)單的不可判定問題★u★u★===**u1u1u1***u2u2u2***u3u3u3******………ununun**u★為將p’轉(zhuǎn)換為PCP的一個(gè)實(shí)例P，做下面的事情：如果P’是如下的簇:t1b1t2b2tkbk,,,…t3b3,設(shè)u=u1u2…un是一個(gè)長(zhǎng)串為n的串。定義如下三個(gè)串：36一個(gè)簡(jiǎn)單的不可判定問題★u★u★===**u1u1u1***一個(gè)簡(jiǎn)單的不可判定問題就令P是如下的簇★t1★b1★★t1b1★★t3b3★,,,…★t2b2★,,★tkbk★

,*

此時(shí)若再將P看PCP的實(shí)例，就可以看到，可能形成匹配的唯一的骨牌是第一個(gè)骨牌★t1★b1★37一個(gè)簡(jiǎn)單的不可判定問題就令P是如下的簇★t1★b1★★因?yàn)樗琼敳亢偷撞恳韵嗤?hào)，即*，開始的唯一的骨牌。除了強(qiáng)迫匹配以第一個(gè)骨牌開始以外，*的使用并不影響可能的匹配，因?yàn)樗鼈儽辉瓉淼姆?hào)相互隔開，原來的符號(hào)現(xiàn)在出現(xiàn)在匹配的偶數(shù)們。骨牌是用來讓頂部在匹配的最后再增加一個(gè)*。一個(gè)簡(jiǎn)單的不可判定問題

*

38因?yàn)樗琼敳亢偷撞恳韵嗤?hào)，即*，開始的唯一的骨牌。除一個(gè)主要內(nèi)容5.1語言理論中的不可判定問題5.2一個(gè)簡(jiǎn)單的不可判定問題5.3映射可歸約性

5.3.1可計(jì)算函數(shù) 5.3.2映射可歸約性的形式定義

39主要內(nèi)容5.1語言理論中的不可判定問題39§5.3映射可歸約性使用規(guī)約技術(shù)可以證明各種問題的不可判定性。本節(jié)將規(guī)約性概念形式化，這樣就能更精確地使用它。將一個(gè)問題歸約為另一個(gè)問題的概念可以用多種方式來形式定義，選擇使用哪種方式要根據(jù)具體應(yīng)用情況。我們的選擇是一種簡(jiǎn)單方式的可歸約性，叫做映射可歸約性。粗略地說，“用映射可歸約性將問題A歸約為問題B”是指，存在一個(gè)可計(jì)算函數(shù)，它將問題A的實(shí)例轉(zhuǎn)換成問題B的實(shí)例。如果有了這樣一個(gè)轉(zhuǎn)換函數(shù)，就能用B的解決方案來解A。原是，A的任何一個(gè)實(shí)例可以這樣來解：首先用這個(gè)歸約將A轉(zhuǎn)換為B的一個(gè)實(shí)例，然后應(yīng)用B的解決方案。40§5.3映射可歸約性使用規(guī)約技術(shù)可以證明各種問題的不可判例5.13整數(shù)上所有通常的算術(shù)運(yùn)算都是可計(jì)算函數(shù)。例如，可以制造一個(gè)機(jī)器，它以<m,n>為輸入且返回m與n的和m+m。定義5.6函數(shù)f：

**是一個(gè)可計(jì)算函數(shù)，如果有圖靈機(jī)M，使得在每個(gè)輸入w上停機(jī)，且此時(shí)只有f(w)出現(xiàn)在帶上。

定義5.12§5.3映射可歸約性圖靈機(jī)計(jì)算函數(shù)的方式是：將函數(shù)的輸入放在帶子上，開始運(yùn)行，并以停機(jī)后的帶子作為函數(shù)的輸出。41例5.13整數(shù)上所有通常的算術(shù)運(yùn)算都是可計(jì)算函數(shù)。定義函例5.14可計(jì)算函數(shù)可以是機(jī)器的描述之間的變換。例如，如果w=<M>是圖靈機(jī)的編碼，可以有一個(gè)可計(jì)算函數(shù)f，以w為輸入，且返回一個(gè)圖靈機(jī)的描述<M>。M是一個(gè)與M識(shí)別相同語言的機(jī)器。函數(shù)f通過在M的描述中加入一些狀態(tài)來完成這個(gè)任務(wù)。如果M不是圖靈機(jī)的合法編碼，f就返回

§5.3映射可歸約性42例5.14可計(jì)算函數(shù)可以是機(jī)器的描述之間的變換。例如，§5.定義5.6語言A是映射可歸約到語言B的，如果存在可計(jì)算函數(shù)f：**使得對(duì)每個(gè)w，w∈A等價(jià)于f(w)∈B記作A≤mB。稱函數(shù)f為A到B的歸約。定義5.15ABff§5.3映射可歸約性A到B的映射規(guī)約提供了將A的成員測(cè)試問題轉(zhuǎn)化為B的成員測(cè)試問題的方法。為了檢查是否有w屬于A，可使這個(gè)規(guī)約f，將w映射到f(w)，然后檢查是否f(w)屬于B。如果一個(gè)問題映射可規(guī)約到第二個(gè)問題，且第二個(gè)問題先前已被解決，那就能得到原來問題的解43定義語言A是映射可歸約到語言B的，如果存在可計(jì)算函定義ABf定義5.6如果A≤mB且B是可判定的，則A也是可判定的。定理5.16§5.3映射可歸約性證明：設(shè)M是B的判定器，f是從A到B的歸約。A的判定器N的描述如下：N=“對(duì)于輸入w：1)計(jì)算f(w)。2)在f(w)上運(yùn)行M，輸出M的輸出。”顯然，如果w∈A，則f(w)∈B，因?yàn)閒是從A到B的歸約。因此，只要w∈A，則M接受f(w)。故N的運(yùn)行正如所求。44定義如果A≤mB且B是可判定的，則A也是可判定的。定理§5.定義5.6

如果A≤mB且A是不可判定的，則B也是不可判定的。

推論5.17例5.18定理5.1使用從ATM出發(fā)的一個(gè)規(guī)約，證明了HALTTM是不可判定的。這個(gè)歸約說明了怎么用HALTTM的判定器給出ATM的判定器。以下展示從ATM到HALTTM的映射可歸約性，為此必須提供一個(gè)可計(jì)算函數(shù)f，它使用形如<M，w>的輸入，返回形如<M，w>的輸出，使得<M，w>∈

ATM當(dāng)且僅當(dāng)<M，w>∈HALTTM

§5.3映射可歸約性45定義如果A≤mB且A是不可判定的，則B也是不可判定的。推下面的機(jī)器F計(jì)算了歸約f:F=“對(duì)于輸入<M，w>：1)構(gòu)造下面圖靈機(jī)M’。M’=“對(duì)于輸入x：a.在x上運(yùn)行M。b.如果M接受，則接受。c.如果M拒絕，則進(jìn)入循環(huán)。2)輸出<M’，w’>。”§5.3映射可歸約性46下面的機(jī)器F計(jì)算了歸約f:§5.3映射可歸約性46例5.19定理5.11中的波斯特對(duì)應(yīng)問題是不可判定的，其證明中包含了兩個(gè)映射歸約。它首先證明了ATM≤mMPCP，然后又證明了MPCP≤mPCP。對(duì)于兩種情形，都能容易地得到實(shí)際的歸約函數(shù)，且能容易地證明它們是映射歸約。例5.20在定理5.4的證明中，隱含了一個(gè)從ETM到EQTM的映射歸約。此歸約f將輸入<M>映射到輸出<M，M1>,其中M1是拒絕所有輸入的機(jī)器。§5.3映射可歸約性47例5.19定理5.11中的波斯特對(duì)應(yīng)問題是不可判定的，例5.21本節(jié)定義了映射可歸約性的形式概念，本章的前面部分所使用的可歸約性都是非形式概念。定理5.2證明ETM是不可判定的，這個(gè)證明說明了映射可歸約性的形式概念與非形式概念之間的差別。ETM的不可判定性是通過將ATM歸約到它來證明的?，F(xiàn)在來看看能否將這個(gè)歸約轉(zhuǎn)化為映射歸約?！?.3映射可歸約性48例5.21本節(jié)定義了映射可歸約性的形式概念，本章的前面如果A≤mB，且B是可圖靈可識(shí)別的，則A也是圖靈可識(shí)別的。

定理5.22推論5.23如果A≤mB，且A不是圖靈可識(shí)別的，則B也不是圖靈可識(shí)別的?！?.3映射可歸約性證明與5.16類似，只是將M和N改為識(shí)別器。49如果A≤mB，且B是可圖靈可識(shí)別的，則A也是圖靈定理推論如果定理5.24EQTM既不是圖靈可識(shí)別的，也不是補(bǔ)圖靈可識(shí)別的。

首先證明EQTM不是圖靈可識(shí)別的。為此，只要證明ATM可歸約到EQTM的補(bǔ)即可。歸約函數(shù)如下：F=“對(duì)于輸入<M，w>，其中M是TM，w是串：1)構(gòu)造下列兩個(gè)機(jī)器M1和M2。M1=“對(duì)于任何輸入：a.拒絕?！盡2=“對(duì)于任何輸入：a.在w上運(yùn)行M,如果它接受，就接受?！?)輸出<M1，M2>?！薄?.3映射可歸約性50定理EQTM既不是圖靈可識(shí)別的，也不是補(bǔ)圖靈可識(shí)別的。首先這里M1什么也沒接受。如果M接受w，則M2接受每一個(gè)輸入，故兩個(gè)機(jī)器不等價(jià)。相反，如果M不接受w，則M2什么也不接受，故它們是等價(jià)的。這樣f將ATM歸約到EQTM的補(bǔ)，這正是我們所希望的。為了證明EQTM的補(bǔ)不是圖靈可識(shí)別的，只要給出一個(gè)從ATM到EQTM的歸約。因此要證明ATM≤mEQTM。下面的TMG計(jì)算歸約函數(shù)g.§5.3映射可歸約性51這里M1什么也沒接受。如果M接受w，則M2接受每一個(gè)輸入，§G=“對(duì)于輸入<M，w>，其中M是TM，w是串：1)構(gòu)造下列兩個(gè)機(jī)器M1和M2.M1=“對(duì)于任何輸入：a.接受?！盡2=“對(duì)于任何輸入：a.在w上運(yùn)行Mb.如果它接受，就接受?！?)輸出<M1，M2>。”

f和g之間的唯一差別在機(jī)器M1上。在f中，機(jī)器M1總是拒絕.而在g中，它總是接受。在f和g中。M接受w當(dāng)且僅當(dāng)M2接受所有串。在g中，M接受

w當(dāng)且僅當(dāng)M1和M2等價(jià)。這就是g是從ATM到EQTM的歸約的原因。§5.3映射可歸約性52G=“對(duì)于輸入<M，w>，其中M是TM，w是串：§5.3作業(yè)5.1、5.5、5.6、5.28、5.3453作業(yè)5.1、5.5、5.6、5.28、5.3453計(jì)算理論第5章可歸約性54計(jì)算理論第5章可歸約性1前言

在第4章已經(jīng)確定采用圖靈機(jī)作為通用計(jì)算器機(jī)的模型，并介紹了幾個(gè)在圖靈機(jī)上可解的問題，還給出了一個(gè)計(jì)算機(jī)不可解的問題，即ATM。本章討論另外幾個(gè)不可解的問題。在討論過程中，將介紹一個(gè)基本方法，可用來證明問題是計(jì)算上不可解的，這個(gè)方法稱為可歸約性。

歸約旨在將一個(gè)問題轉(zhuǎn)化為另一個(gè)問題，且使得可以用第二個(gè)問題的解來解第一個(gè)問題，在日常生活中，雖然不這樣稱呼，但時(shí)常會(huì)遇見可歸約性問題。

55前言在第4章已經(jīng)確定采用圖靈機(jī)作為通用計(jì)算器機(jī)前言例如，在一個(gè)新城市中認(rèn)路，如果有一張地圖，事情就容易了。這樣，就將在城市認(rèn)路問題歸約為得到地圖問題?？蓺w約性總是涉及兩個(gè)問題，稱之為A和B。如果A可歸約到B，就可用B的解來解A。在上述例子中，A是城市認(rèn)路問題，B是得到地圖問題。注意，可歸約性說的不是怎樣去解A或B，而是在知道B的解時(shí)怎么去解A。56前言例如，在一個(gè)新城市中認(rèn)路，如果有一張地圖，事情就容易了。主要內(nèi)容5.1語言理論中的不可判定問題5.2一個(gè)簡(jiǎn)單的不可判定問題5.3映射可歸約性

5.3.1可計(jì)算函數(shù) 5.3.2映射可歸約性的形式定義

57主要內(nèi)容5.1語言理論中的不可判定問題4語言理論中的不可判定問題ATM是不可判定的，即確定個(gè)圖靈機(jī)是否接受一個(gè)給定的輸入問題是不可判定的。下面考慮一個(gè)與之相關(guān)的問題：HALTTM，即確定一個(gè)圖靈機(jī)對(duì)給定輸入是否停機(jī)（通過接受或拒絕）問題。若將ATM歸約到HALTTM，就可以利用ATM的不可判定性證明HALTTM的不可判定性。設(shè):

HALTTM={<M,w>|M是一個(gè)TM,且對(duì)輸入w停機(jī)}58語言理論中的不可判定問題ATM是不可判定的，即確定個(gè)圖靈機(jī)是語言理論中的不可判定問題定理5.1HALTTM是不可判定的。

為得到矛盾，假設(shè)TMR判定HALTTM，由之可以構(gòu)造TMS來判定ATM,其構(gòu)造如下：S=“在輸入<M，w>上，此處<M，w>是TMM和串w的編碼：1)在輸入<M，w>上運(yùn)行TMR。2)如果R拒絕，則拒絕。3)如果R接受，則在w上模擬M，直到它停機(jī)。4)如果M已經(jīng)接受，則接受；如果M已經(jīng)拒絕，則拒絕。顯然，如果R判定HALTTM，則S判定ATM。因?yàn)锳TM是不可判定的，故HALTTM也必定是不可判定的。反證法，假設(shè)可判定，證明ATM是可判定的。59語言理論中的不可判定問題定理HALTTM是不可判定的。為得語言理論中的不可判定問題定理5.2ETM是不可判定的。

先用標(biāo)準(zhǔn)術(shù)語來寫在證明思路中描述的那上修改型機(jī)器M1.M1=“在輸入x上：1)如果x≠w，則拒絕。2)如果x=w，則在x上運(yùn)行M，當(dāng)M接受時(shí)，就接受?！边@個(gè)機(jī)器以w作為它的描述的一部分。檢查x=w是否成立的方法很顯然，即掃描輸入并用一個(gè)字符一個(gè)字符地將它與w進(jìn)行比較，就可確定它們是否相同。

反證法，假設(shè)可判定，證明ATM是可判定的。除w外M1拒絕所有串60語言理論中的不可判定問題定理ETM是不可判定的。語言理論中的不可判定問題再假設(shè)TMR判定ETM。如下構(gòu)造判定ATM的TMS:S=“在輸入<M，w>上，此處<M，w>是TMM和串w的編碼：1)用M和w的描述來構(gòu)造上述TMM1。2)在輸入<M1>上運(yùn)行R。3)如果R接受，則拒絕；如果R拒絕，則接受?！辈豢?，M接受w說明L(M1)是空集，因此M1不接受w61語言理論中的不可判定問題再假設(shè)TMR判定ETM。如下構(gòu)造判語言理論中的不可判定問題另一個(gè)與圖靈機(jī)有關(guān)的計(jì)算問題也很有意思，該問題是：給定一個(gè)圖靈機(jī)和一個(gè)可由某個(gè)更簡(jiǎn)單的計(jì)算模型識(shí)別的語言，測(cè)定此圖靈機(jī)是否識(shí)別此語言。例如：令REGULARTM是測(cè)定一個(gè)給定的圖機(jī)是否有一個(gè)與之等價(jià)的有窮自動(dòng)機(jī)問題，則這個(gè)問題與測(cè)定一個(gè)給定的圖靈機(jī)是否識(shí)別一個(gè)與此正則語言的問題相同。設(shè)：

REGULARTM={<M>|M是一個(gè)TM，且L(M)是一個(gè)正則語言}62語言理論中的不可判定問題另一個(gè)與圖靈機(jī)有關(guān)的計(jì)算問題也很有意語言理論中的不可判定問題定理5.3

REGULARTM是不可判定的。設(shè)R是判定REGULARTM的一個(gè)TM，下面構(gòu)造判定ATM的TMS。S的運(yùn)行方式如下：S=“對(duì)于輸入<M，w>，其中M是TM，w是串：1)構(gòu)造下述TMM2：M2=“在輸入x上：a)如果x具有形式0n1n，則接受。b)如果x不具有此形式，則在輸入w上運(yùn)行M。如果M接受w，則接受。”2)在輸入<M2>上運(yùn)行R。3)如果R接受，則接受；如果R拒絕，則拒絕。”63語言理論中的不可判定問題定理REGULARTM是不可判定的語言理論中的不可判定問題定理5.4EQTM是不可判定的。

設(shè)TMR判定EQTM。如下構(gòu)造判定ETM的TMS：S=“對(duì)于輸入<M>，其中M是TM：1)在輸入<M，M1>上運(yùn)行R，其中M1是拒絕所有輸入的圖靈機(jī)。2)如果R接受，則接受；如果R拒絕，則拒絕。如果R判定EQTM，則S判定ETM。但由定理5.2，ETM是不可判定的，故EQTM也是不可判定的。64語言理論中的不可判定問題定理EQTM是不可判定的。設(shè)TM語言理論中的不可判定問題定義5.5

設(shè)M是一個(gè)圖靈機(jī)，w是一個(gè)串。M在w上的一個(gè)

接受計(jì)算歷史是一個(gè)格局序列C1，C2，．．．,Cl，其中C1是M在w上的起始格局，Cl是M的一個(gè)接受格局，且每個(gè)Ci都是Ci-1的合法結(jié)果，即符合M的規(guī)則。M在w上的一拒絕計(jì)算歷史可類似定義，只是Cl應(yīng)是一個(gè)拒絕格局。65語言理論中的不可判定問題定義設(shè)M是一個(gè)圖靈機(jī)，定義5.6

線性界限自動(dòng)機(jī)是一種受到限制的圖靈機(jī)，它不允許其讀寫頭離開包含輸入的帶區(qū)域。如果此機(jī)器試圖將它的讀寫頭移出輸入的兩個(gè)端點(diǎn)，則讀寫頭就保持在原地不動(dòng)。這與普通圖靈機(jī)的讀寫頭不會(huì)離開帶子的左端點(diǎn)的方式一樣。語言理論中的不可判定問題定義5.6ababa控制器66定義線性界限自動(dòng)機(jī)是一種受到限制的圖靈機(jī)，它不允語言理論中定義5.6設(shè)M是有q個(gè)狀態(tài)和g個(gè)帶符號(hào)的LBA。對(duì)于長(zhǎng)度為n的帶子，M恰有qngn個(gè)不同的格局。語言理論中的不可判定問題引理5.7

M的格局就像計(jì)算中間的一快照。格局由控制狀態(tài)、讀寫頭位置和帶內(nèi)容組成。這里，M有q個(gè)狀態(tài)。它的帶長(zhǎng)度是n，所以讀寫頭可能處于n個(gè)位置之一，且gn多個(gè)帶符號(hào)串可能出現(xiàn)在帶上。此三個(gè)量的乘積就是帶長(zhǎng)為n的M的格局總數(shù)。

67定義設(shè)M是有q個(gè)狀態(tài)和g個(gè)帶符號(hào)的LBA。對(duì)于長(zhǎng)度為語言理定義5.6ALBA是可判定的。

語言理論中的不可判定問題定理5.8證明判定ALBA的算法如下：L=“對(duì)于輸入<M，w>，其中M是LBA，w是串：1)在w上模擬Mqngn步，或者直到它停機(jī)。2)如果M停機(jī)，則當(dāng)它接受時(shí)接受，拒絕時(shí)拒絕。如果它還沒有停機(jī)，就拒絕?！比绻鸐在w上運(yùn)行qngn步還沒有停機(jī)，根據(jù)引理5.7，它必定在重復(fù)某個(gè)格局，即陷入了循環(huán)。這就是算法為什么在此情形下拒絕的原因。68定義ALBA是可判定的。語言理論中的不可判定問題定理證明定義5.6

ELBA是不可判定的。

語言理論中的不可判定問題定理5.9現(xiàn)在構(gòu)造從ATM到ELBA的歸約。假設(shè)TMR判定ELBA。如下構(gòu)造判定ATM的TMS：S=“對(duì)于輸入<M，w>，其中M是TM，w是串：1)如在證明思路中所描述的那樣從M和w構(gòu)造LBAB。2)在輸入<B>上運(yùn)行R。3)如果R拒絕，則接受；如果R接受，則拒絕?！?/p>

####…##C1C2C3Cl69定義ELBA是不可判定的。語言理論中的不可判定問題定理如果R接受<B>，則L(B)=。這樣，M在w上就沒接受計(jì)算歷史，M也就不接受w.因此，S也就拒絕<M，w>。類似地，如果R拒絕<B>，則B的語言不空。B能夠接受的唯一串是M在w上的接受計(jì)算歷史。這樣，M必定接受w。相應(yīng)地，S也就接受<M，w>。下圖是檢查這樣一個(gè)TM計(jì)算歷史的示意圖。

語言理論中的不可判定問題q3ab#xxq5b#……#xBCiCi+170如果R接受<B>，則L(B)=。這樣，M在w上就沒接使用利用計(jì)算歷史的歸約技術(shù)，還能建立有關(guān)上下文無關(guān)文法和下推自動(dòng)機(jī)問題的不可判定性。加快一下，定理4.7介紹了一個(gè)算法來判定一個(gè)上下文無關(guān)文法是否派生串，即判定L(G)=是否成立。與此相關(guān)，現(xiàn)在要證明問題“測(cè)定一個(gè)上下文無關(guān)文法是否派生所有可能的串”是不可判定的。證明這個(gè)問題不可判定是證明上下文無關(guān)文法等價(jià)性問題不可判定的重要步驟。設(shè):ALLCFG={<G>|G是一個(gè)CFG且L(G)=*}語言理論中的不可判定問題71使用利用計(jì)算歷史的歸約技術(shù)，還能建立有關(guān)上下文無關(guān)文語言理論定義5.6ALLCFG是不可判定的。

語言理論中的不可判定問題定理5.10用反證法。為得到矛盾，假設(shè)ALLCFG是可判定的，用這個(gè)假設(shè)來證明ATM是可判定的。其證明與定理5.9的證明類似，只是稍微復(fù)雜一些，繞了一點(diǎn)點(diǎn)彎。這是一個(gè)從ATM出發(fā)利用計(jì)算歷史的歸約。但由于技術(shù)上的原因，對(duì)計(jì)算歷史的表示做了些修改，后面將解釋這樣做的原因。現(xiàn)在來描述怎樣運(yùn)用ALLCFG的判定過程來判定ATM。對(duì)于TMM和輸入串w，首先構(gòu)造一個(gè)CFGG，使得它派生所有串當(dāng)且僅當(dāng)M不接受w。所以，如果M接受w，則存在一個(gè)特別的串，G不派生它。這個(gè)串應(yīng)該是M在w上的計(jì)算歷史。即：設(shè)計(jì)G，使之派生所有不是M在w上接受計(jì)算歷史的串。

72定義ALLCFG是不可判定的。語言理論中的不可判定問題定語言理論中的不可判定問題為了使得CFGG派生所有不是M在w上接受計(jì)算歷史的串，采用下的策略。一個(gè)串不能成為M在w上的接受計(jì)算歷史的原因可能有多個(gè)。將M在w上的接受計(jì)算歷史表示成#C1#C2#...#Cl#，其中Ci是M在w上計(jì)算的第i步的格局。然后G派生出滿足下述條件的所有串：1)不以Cl開始。2)不以一個(gè)接受格局結(jié)束3)在M的規(guī)則下，某個(gè)Ci不恰好派生Ci+1。如果M不接受w，就沒有接受計(jì)算歷史存在，故所有串都因?yàn)檫@樣或那樣的問題而不能成為接受計(jì)算歷史，因此G將派生所有串，這正是所希望的。73語言理論中的不可判定問題為了使得CFGG派生所有不是M在w語言理論中的不可判定問題這個(gè)思路存在的問題是：當(dāng)D將Ci彈出棧時(shí)，它處于相反的左右為難，因而不適合與Ci+1比較。前面提到的繞彎就在此處。換一種方法來寫接受計(jì)算歷史，使得每隔一個(gè)格局就以相反的順序出現(xiàn)。奇數(shù)位置保持以向前的順序?qū)?，但偶?shù)位置向后寫。這種形式的一個(gè)接受計(jì)算歷史如下圖所示：

####…##C1C2RC3C4R#Cl74語言理論中的不可判定問題這個(gè)思路存在的問題是：當(dāng)D將Ci彈出主要內(nèi)容5.1語言理論中的不可判定問題5.2一個(gè)簡(jiǎn)單的不可判定問題5.3映射可歸約性

5.3.1可計(jì)算函數(shù) 5.3.2映射可歸約性的形式定義

75主要內(nèi)容5.1語言理論中的不可判定問題22本節(jié)將證明：不可判定性現(xiàn)象不僅能僅能局限于有限自動(dòng)機(jī)的問題，我們將給出一個(gè)關(guān)于串操作的不可判定問題，稱為波斯特對(duì)應(yīng)問題?？梢院苋菀椎貙⑦@個(gè)問題描述成一種游戲，多米諾骨牌。每個(gè)骨牌由兩個(gè)串構(gòu)成，一邊一個(gè)，單個(gè)骨牌看上去像一簇骨牌看起來像任務(wù)是將這些骨牌進(jìn)行排列(允許重復(fù))，使得在總計(jì)頂部符號(hào)后得到的串與總計(jì)詢問符號(hào)后得到的串相同。這樣的排列稱為一個(gè)匹配。例如，下面的排列就是這個(gè)游戲的一個(gè)匹配。一個(gè)簡(jiǎn)單的不可判定問題aabbcaaabcaaabcc,,,76本節(jié)將證明：不可判定性現(xiàn)象不僅能僅能局限于有限自動(dòng)機(jī)的問題，一個(gè)簡(jiǎn)單的不可判定問題aabbcacaaaababcc閱讀頂部后得到的串a(chǎn)bcaaabc，與總計(jì)詢問后得到的本同?？梢詫⒐桥谱冃问沟煤驮儐枌?duì)應(yīng)符號(hào)整齊地排列，以此更容易表示匹配。aabbccaaaaaabbcc77一個(gè)簡(jiǎn)單的不可判定問題aabbcacaaaababcc閱讀頂一個(gè)簡(jiǎn)單的不可判定問題

對(duì)某些骨牌簇，不可能找到這樣的匹配。例如，簇

不可能包含匹配，因?yàn)轫敳康拿總€(gè)串都比詢問對(duì)應(yīng)的串長(zhǎng)。波斯特對(duì)應(yīng)問題是：確定一簇骨牌是否有一個(gè)匹配。這個(gè)問題在算法上是不可解的。

abcabcacaccba,,78一個(gè)簡(jiǎn)單的不可判定問題對(duì)某些骨牌簇，不可能找到一個(gè)簡(jiǎn)單的不可判定問題在形式描述這個(gè)問題和給出它的證明之前，先來精確地描述這個(gè)問題，然后表示成一個(gè)。骨牌簇P是pcp的一個(gè)實(shí)例：

匹配是一個(gè)序列i1，i2，．．．，il，使ti1ti2．．．til=bi1bi2bil.問題是確定P是否有匹配。令PCP={<G>|P是波斯特對(duì)應(yīng)問題的一個(gè)實(shí)例，且P有匹配}

t1b1t2b2tkbk,,P=,…79一個(gè)簡(jiǎn)單的不可判定問題在形式描述這個(gè)問題和給出它的證定義5.6

PCP是不可判定的。

一個(gè)簡(jiǎn)單的不可判定問題定理5.11假設(shè)TMR判定PCP。構(gòu)造S來判定ATM。令M=(Q,,,,q0,qaccept,qreject)其中Q,,,分別是M的狀態(tài)集、輸入字母表、帶字母表和轉(zhuǎn)移函數(shù)。S構(gòu)造PCP的一個(gè)實(shí)例P，使得P有一個(gè)匹配當(dāng)且僅當(dāng)M接受w。為此，S首先構(gòu)造MPCP的一個(gè)實(shí)例P’。下面以七個(gè)部分來描述這個(gè)構(gòu)造。每個(gè)部分完成在w上模擬M的一個(gè)特定方面。在構(gòu)造過程中，為了解釋我們正在做什么，用一個(gè)例子插在構(gòu)造中。80定義PCP是不可判定的。一個(gè)簡(jiǎn)單的不可判定問題定理假設(shè)T一個(gè)簡(jiǎn)單的不可判定問題

第1部分：構(gòu)造以下方式開始：

將放入p’作為第一張骨牌

因?yàn)镻’是MPCP的一個(gè)實(shí)例，故匹配必須以這張骨牌開始。底部串以M在w上接受計(jì)算歷史中的第一個(gè)格局C1=q0w1w2．．．wn開始。如圖所示:##q0w1w2…wn#t1b1##…q0w1w2wn#81一個(gè)簡(jiǎn)單的不可判定問題第1部分：構(gòu)造以下方式開始：一個(gè)簡(jiǎn)單的不可判定問題

到目前為止，只得到一個(gè)部分匹配，其詢問串由C1=

＃q0w1w2．．．wn＃構(gòu)成，頂部串只有#。為獲得匹配，盤面擴(kuò)展串來匹配詢問串。用新骨牌來作這樣的擴(kuò)展。這些新的骨牌強(qiáng)迫模擬M的一次單步運(yùn)行，使得M的一下個(gè)格局出現(xiàn)在詢問串的擴(kuò)展中。第2、3、4部分在P’中增加的骨牌在模擬中起主要作用。第2部分處理讀寫向右運(yùn)動(dòng)，第3部分處理讀寫頭向左運(yùn)動(dòng)，第4部分處理不與讀寫關(guān)相鄰的帶方格。82一個(gè)簡(jiǎn)單的不可判定問題到目前為止，只得到一個(gè)部分匹配一個(gè)簡(jiǎn)單的不可判定問題第2部分：對(duì)于第一個(gè)a,b∈和q,r∈Q，其中q≠qreject，如果(q,a)=(r,b,R),則將放入P’中。第3部分：對(duì)于第一個(gè)a,b,c∈和q,r∈Q，其中q≠qreject，如果(q,a)=(r,b,L)，則將放入p’中。第4部分：對(duì)于每一個(gè)a∈，將放入p’中。這樣，第2、3和4部分的骨牌，使得我們能夠通過“在第一個(gè)格局之后增加第二個(gè)格局”的方法來擴(kuò)展匹配。希望這個(gè)過程能夠繼續(xù)下去，即增加第三個(gè)格局，然后第四個(gè)格局，等等。為此，需要增加一個(gè)新的骨牌來復(fù)制符號(hào)#。qabrcqarcbaa83一個(gè)簡(jiǎn)單的不可判定問題第2部分：對(duì)于第一個(gè)a,b∈和q,一個(gè)簡(jiǎn)單的不可判定問題第5部分：將和放入P’中接著上面的例子。假設(shè)在狀態(tài)q7且讀1時(shí)，M進(jìn)入狀q5，在帶上寫下0，并將讀寫頭向右移到。即(q7,1)=(q5,0,R)。則在P’中有骨牌最后的那個(gè)匹配被擴(kuò)展到#_###q710q520q500#q7##22q7110000##…84一個(gè)簡(jiǎn)單的不可判定問題第5部分：將一個(gè)簡(jiǎn)單的不可判定問題再假設(shè)在狀態(tài)q5且讀0時(shí)，M進(jìn)入狀態(tài)q9，在帶上寫下2，并將它的讀寫頭向左移動(dòng)。故(q5,1)=(q9,2,L)。則有骨牌第一個(gè)骨牌與本構(gòu)造部分有關(guān)，因?yàn)樽x寫頭左邊的符號(hào)是0。前面的部分匹配就被擴(kuò)展成

0q50q9021q50q9122q50q922_q50q9_2,,和2q9020#0##220q5q50000##…85一個(gè)簡(jiǎn)單的不可判定問題再假設(shè)在狀態(tài)q5且讀0時(shí)，M進(jìn)入狀態(tài)q一個(gè)簡(jiǎn)單的不可判定問題注意，構(gòu)造匹配就是在w上模擬M，這個(gè)過程要一直進(jìn)行到M到達(dá)停機(jī)狀態(tài)。如果出現(xiàn)了接受狀態(tài)，希望這個(gè)部分匹配的頂部“趕上”底部，從而使得這個(gè)匹配得以完成。為此，再增加加下骨牌。第6部分：對(duì)于第一個(gè)a∈，將和放入P’中這個(gè)步驟的效果是：在圖靈機(jī)停機(jī)后增加一些“偽步驟”。這里，讀寫頭“吃掉”一些鄰近的符號(hào)直到?jīng)]有符號(hào)剩下。再繼續(xù)前面的例子，假設(shè)到機(jī)器以接受狀態(tài)停機(jī)的地方為止的部分匹配是aqacceptqacceptqacceptaqaccept86一個(gè)簡(jiǎn)單的不可判定問題注意，構(gòu)造匹配就是在w上模擬M，這個(gè)過一個(gè)簡(jiǎn)單的不可判定問題剛才增加的骨牌允許匹配如下繼續(xù)進(jìn)行：##…21qaccept2#021qaccept2###2211qacceptqaccept0022##…#……#qaccept#87一個(gè)簡(jiǎn)單的不可判定問題剛才增加的骨牌允許匹配如下繼續(xù)進(jìn)行：#一個(gè)簡(jiǎn)單的不可判定問題第7部分：最的增加如下骨牌來完成匹配：##q0w1w2…wn####qacceptqaccept…###88一個(gè)簡(jiǎn)單的不可判定問題第7部分：最的增加如下骨牌一個(gè)簡(jiǎn)單的不可判定問題★u★u★===**u1u1u1***u2u2u2***u3u3u3******………ununun**u★為將p’轉(zhuǎn)換為PCP的一個(gè)實(shí)例P，做下面的事情：如果P’是如下的簇:t1b1t2b2tkbk,,,…t3b3,設(shè)u=u1u2…un是一個(gè)長(zhǎng)串為n的串。定義如下三個(gè)串：89一個(gè)簡(jiǎn)單的不可判定問題★u★u★===**u1u1u1***一個(gè)簡(jiǎn)單的不可判定問題就令P是如下的簇★t1★b1★★t1b1★★t3b3★,,,…★t2b2★,,★tkbk★

,*

此時(shí)若再將P看PCP的實(shí)例，就可以看到，可能形成匹配的唯一的骨牌是第一個(gè)骨牌★t1★b1★90一個(gè)簡(jiǎn)單的不可判定問題就令P是如下的簇★t1★b1★★因?yàn)樗琼敳亢偷撞恳韵嗤?hào)，即*，開始的唯一的骨牌。除了強(qiáng)迫匹配以第一個(gè)骨牌開始以外，*的使用并不影響可能的匹配，因?yàn)樗鼈儽辉瓉淼姆?hào)相互隔開，原來的符號(hào)現(xiàn)在出現(xiàn)在匹配的偶數(shù)們。骨牌是用來讓頂部在匹配的最后再增加一個(gè)*。一個(gè)簡(jiǎn)單的不可判定問題

*

91因?yàn)樗琼敳亢偷撞恳韵嗤?hào)，即*，開始的唯一的骨牌。除一個(gè)主要內(nèi)容5.1語言理論中的不可判定問題5.2一個(gè)簡(jiǎn)單的不可判定問題5.3映射可歸約性

5.3.1可計(jì)算函數(shù) 5.3.2映射可歸約性的形式定義

92主要內(nèi)容5.1語言理論中的不可判定問題39§5.3映射可歸約性使用規(guī)約技術(shù)可以證明各種問題的不可判定性。本節(jié)將規(guī)約性概念形式化，這樣就能更精確地使用它。將一個(gè)問題歸約為另一個(gè)問題的概念可以用多種方式來形式定義，選擇使用哪種方式要根據(jù)具體應(yīng)用情況。我們的選擇是一種簡(jiǎn)單方式的可歸約性，叫做映射可歸約性。粗略地說，“用映射可歸約性將問題A歸約為問題B”是指，存在一個(gè)可計(jì)算函數(shù)，它將問題A的實(shí)例轉(zhuǎn)換成問題B的實(shí)例。如果有了這樣一個(gè)轉(zhuǎn)換函數(shù)，就能用B的解決方案來解A。原是，A的任何一個(gè)實(shí)例可以這樣來解：首先用這個(gè)歸約將A轉(zhuǎn)換為B的一個(gè)實(shí)例，然后應(yīng)用B的解決方案。93§5.3映射可歸約性使用規(guī)約技術(shù)可以證明各種問題的不可判例5.13整數(shù)上所有通常的算術(shù)運(yùn)算都是可計(jì)算函數(shù)。例如，可以制造一個(gè)機(jī)器，它以<m,n>為輸入且返回m與n的和m+m。定義5.6函數(shù)f：

**是一個(gè)可計(jì)算函數(shù)，如果有圖靈機(jī)M，使得在每個(gè)輸入w上停機(jī)，且此時(shí)只有f(w)出現(xiàn)在帶上。

定義5.12§5.3映射可歸約性圖靈機(jī)計(jì)算函數(shù)的方式是：將函數(shù)的輸入放在帶子上，開始運(yùn)行，并以停機(jī)后的帶子作為函數(shù)的輸出。94例5.13整數(shù)上所有通常的算術(shù)運(yùn)算都是可計(jì)算函數(shù)。定義函例5.14可計(jì)算函數(shù)可以是機(jī)器的描述之間的變換。例如，如果w=<M>是圖靈機(jī)的編碼，可以有一個(gè)可計(jì)算函數(shù)f，以w為輸入，且返回一個(gè)圖靈機(jī)的描述<M>。M是一個(gè)與M識(shí)別相同語言的機(jī)器。函數(shù)f通過在M的描述中加入一些狀態(tài)來完成這個(gè)任務(wù)。如果M不是圖靈機(jī)的合法編碼，f就返回

§5.3映射可歸約性95例5.14可計(jì)算函數(shù)可以是機(jī)器的描述之間的變換。例如，§5.定義5.6語言A是映射可歸約到語言B的，如果存在可計(jì)算函數(shù)f：**使得對(duì)每個(gè)w，w∈A等價(jià)于f(w)∈B