計算理論第5章可歸約性1計算理論第5章可歸約性1前言

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

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

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

5.3.1可計算函數 5.3.2映射可歸約性的形式定義

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

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

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

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

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

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

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

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

設M是一個圖靈機，w是一個串。M在w上的一個

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

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

M的格局就像計算中間的一快照。格局由控制狀態、讀寫頭位置和帶內容組成。這里，M有q個狀態。它的帶長度是n，所以讀寫頭可能處于n個位置之一，且gn多個帶符號串可能出現在帶上。此三個量的乘積就是帶長為n的M的格局總數。

14定義設M是有q個狀態和g個帶符號的LBA。對于長度為語言理定義5.6ALBA是可判定的。

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

ELBA是不可判定的。

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

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

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

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

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

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

5.3.1可計算函數 5.3.2映射可歸約性的形式定義

22主要內容5.1語言理論中的不可判定問題22本節將證明：不可判定性現象不僅能僅能局限于有限自動機的問題，我們將給出一個關于串操作的不可判定問題，稱為波斯特對應問題?？梢院苋菀椎貙⑦@個問題描述成一種游戲，多米諾骨牌。每個骨牌由兩個串構成，一邊一個，單個骨牌看上去像一簇骨牌看起來像任務是將這些骨牌進行排列(允許重復)，使得在總計頂部符號后得到的串與總計詢問符號后得到的串相同。這樣的排列稱為一個匹配。例如，下面的排列就是這個游戲的一個匹配。一個簡單的不可判定問題aabbcaaabcaaabcc,,,23本節將證明：不可判定性現象不僅能僅能局限于有限自動機的問題，一個簡單的不可判定問題aabbcacaaaababcc閱讀頂部后得到的串abcaaabc，與總計詢問后得到的本同?？梢詫⒐桥谱冃问沟煤驮儐枌栒R地排列，以此更容易表示匹配。aabbccaaaaaabbcc24一個簡單的不可判定問題aabbcacaaaababcc閱讀頂一個簡單的不可判定問題

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

不可能包含匹配，因為頂部的每個串都比詢問對應的串長。波斯特對應問題是：確定一簇骨牌是否有一個匹配。這個問題在算法上是不可解的。

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

匹配是一個序列i1，i2，．．．，il，使ti1ti2．．．til=bi1bi2bil.問題是確定P是否有匹配。令PCP={<G>|P是波斯特對應問題的一個實例，且P有匹配}

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

PCP是不可判定的。

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

第1部分：構造以下方式開始：

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

因為P’是MPCP的一個實例，故匹配必須以這張骨牌開始。底部串以M在w上接受計算歷史中的第一個格局C1=q0w1w2．．．wn開始。如圖所示:##q0w1w2…wn#t1b1##…q0w1w2wn#28一個簡單的不可判定問題第1部分：構造以下方式開始：一個簡單的不可判定問題

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

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

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

,*

此時若再將P看PCP的實例，就可以看到，可能形成匹配的唯一的骨牌是第一個骨牌★t1★b1★37一個簡單的不可判定問題就令P是如下的簇★t1★b1★★因為它是頂部和底部以相同符號，即*，開始的唯一的骨牌。除了強迫匹配以第一個骨牌開始以外，*的使用并不影響可能的匹配，因為它們被原來的符號相互隔開，原來的符號現在出現在匹配的偶數們。骨牌是用來讓頂部在匹配的最后再增加一個*。一個簡單的不可判定問題

*

38因為它是頂部和底部以相同符號，即*，開始的唯一的骨牌。除一個主要內容5.1語言理論中的不可判定問題5.2一個簡單的不可判定問題5.3映射可歸約性

5.3.1可計算函數 5.3.2映射可歸約性的形式定義

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

**是一個可計算函數，如果有圖靈機M，使得在每個輸入w上停機，且此時只有f(w)出現在帶上。

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

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

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

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

ATM當且僅當<M，w>∈HALTTM

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

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

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

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

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

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

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

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

5.3.1可計算函數 5.3.2映射可歸約性的形式定義

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

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

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

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

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

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

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

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

設M是一個圖靈機，w是一個串。M在w上的一個

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

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

M的格局就像計算中間的一快照。格局由控制狀態、讀寫頭位置和帶內容組成。這里，M有q個狀態。它的帶長度是n，所以讀寫頭可能處于n個位置之一，且gn多個帶符號串可能出現在帶上。此三個量的乘積就是帶長為n的M的格局總數。

67定義設M是有q個狀態和g個帶符號的LBA。對于長度為語言理定義5.6ALBA是可判定的。

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

ELBA是不可判定的。

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

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

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

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

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

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

5.3.1可計算函數 5.3.2映射可歸約性的形式定義

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

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

不可能包含匹配，因為頂部的每個串都比詢問對應的串長。波斯特對應問題是：確定一簇骨牌是否有一個匹配。這個問題在算法上是不可解的。

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

匹配是一個序列i1，i2，．．．，il，使ti1ti2．．．til=bi1bi2bil.問題是確定P是否有匹配。令PCP={<G>|P是波斯特對應問題的一個實例，且P有匹配}

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

PCP是不可判定的。

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

第1部分：構造以下方式開始：

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

因為P’是MPCP的一個實例，故匹配必須以這張骨牌開始。底部串以M在w上接受計算歷史中的第一個格局C1=q0w1w2．．．wn開始。如圖所示:##q0w1w2…wn#t1b1##…q0w1w2wn#81一個簡單的不可判定問題第1部分：構造以下方式開始：一個簡單的不可判定問題

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

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

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

,*

此時若再將P看PCP的實例，就可以看到，可能形成匹配的唯一的骨牌是第一個骨牌★t1★b1★90一個簡單的不可判定問題就令P是如下的簇★t1★b1★★因為它是頂部和底部以相同符號，即*，開始的唯一的骨牌。除了強迫匹配以第一個骨牌開始以外，*的使用并不影響可能的匹配，因為它們被原來的符號相互隔開，原來的符號現在出現在匹配的偶數們。骨牌是用來讓頂部在匹配的最后再增加一個*。一個簡單的不可判定問題

*

91因為它是頂部和底部以相同符號，即*，開始的唯一的骨牌。除一個主要內容5.1語言理論中的不可判定問題5.2一個簡單的不可判定問題5.3映射可歸約性

5.3.1可計算函數 5.3.2映射可歸約性的形式定義

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

**是一個可計算函數，如果有圖靈機M，使得在每個輸入w上停機，且此時只有f(w)出現在帶上。

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

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