計(jì)算理論導(dǎo)引可歸約性

計(jì)算理論導(dǎo)引可歸約性1第一頁，共三十頁，2022年，8月28日前言本章討論另外幾個(gè)不可解的問題。在討論過程中，將介紹一個(gè)基本方法，可用來證明問題是計(jì)算上不可解的，這個(gè)方法稱為可歸約性。歸約旨在將一個(gè)問題轉(zhuǎn)化為加一個(gè)問題，且使得可以用第二個(gè)問題的解來解第一個(gè)問題，在日常生活中，雖然不這樣稱呼，但時(shí)常會(huì)遇見可歸約性問題。例如，在一個(gè)新城市中認(rèn)路，如果有一張地圖，事情就容易了。這樣，就將在城市認(rèn)路問題歸約為得到地圖問題。從波士頓到巴黎旅行，可歸約到兩個(gè)城市的飛機(jī)票，進(jìn)而歸約到找工作問題。數(shù)學(xué)上的例子更多。2第二頁，共三十頁，2022年，8月28日前言ABCDb5b2b1b3b4b7b6BCADb6b2b5b7b4b1b33第三頁，共三十頁，2022年，8月28日前言可歸約性總是涉及兩個(gè)問題，稱之為A和B。如果A可歸約到B，就可用B的解來解A。可歸約性說的不是怎樣去解A或B，而是在知道B的解時(shí)怎么去解A。歸約的目的在于：將一個(gè)問題轉(zhuǎn)化為另一個(gè)問題；且用第二個(gè)問題的解來解第一個(gè)問題。歸約的應(yīng)用（A可歸約到B）如果B是可判定的，則A也是可判定的。如果A是不可判定的，則B也是不可判定的。4第四頁，共三十頁，2022年，8月28日主要內(nèi)容5.1語言理論中的不可判定問題5.2一個(gè)簡單的不可判定問題（自學(xué)）5.3映射可歸約性

5.3.1可計(jì)算函數(shù)

5.3.2映射可歸約性的形式定義

5第五頁，共三十頁，2022年，8月28日語言理論中的不可判定問題ATM={<M,w>|M是一個(gè)TM，且接受w

}ATM是不可判定的，即確定一個(gè)圖靈機(jī)是否接受一個(gè)給定的輸入問題是不可判定的。下面考慮一個(gè)與之相關(guān)的問題：HALTTM，即確定一個(gè)圖靈機(jī)對(duì)給定輸入是否停機(jī)（通過接受或拒絕）問題。若將ATM歸約到HALTTM，就可以利用ATM的不可判定性證明HALTTM的不可判定性。HALTTM的形式化描述

HALTTM={<M,w>|M是一個(gè)TM,且對(duì)輸入w停機(jī)}6第六頁，共三十頁，2022年，8月28日HALTTM是不可判定的定理5.1HALTTM是不可判定的。

證明思路：反證法。（將ATM歸約到HALTTM

）假設(shè)TMR判定HALTTM，利用R可以構(gòu)造一個(gè)判定ATM的TMS。使用R，可以檢查M對(duì)w

是否停機(jī)，如果M對(duì)

w

不停機(jī)，S就拒絕，因?yàn)?lt;M,w>不在ATM中。如果M對(duì)w確實(shí)停機(jī)，S就模擬它，而不會(huì)有死循環(huán)的危險(xiǎn)。這樣，如果TMR存在，就能判定ATM。7第七頁，共三十頁，2022年，8月28日語言理論中的不可判定問題定理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也必定是不可判定的。8第八頁，共三十頁，2022年，8月28日語言理論中的不可判定問題定理5.2ETM是不可判定的。

假設(shè)ETM是可判定的，以此證明ATM

是可判定的。設(shè)R是判定ETM

的一個(gè)TM，考慮用R來構(gòu)造判定ATM

的S。當(dāng)S收到輸入<M,w>時(shí)，如何運(yùn)行？構(gòu)造S的一個(gè)想法是：輸入<M>上運(yùn)行R且看它是否接受。如果是，知道L(M)是空集，因此M不接受w。如果R拒絕w，則只知道L(M)不空，即M接受某個(gè)串，但是不知道是否接受這個(gè)特定的w。因此，不能在<M>上運(yùn)行R。目標(biāo)：修改<M>，使得除了w

外，M對(duì)所有串都拒絕。ETM={M|M是一個(gè)TM，且L(M)=}空問題9第九頁，共三十頁，2022年，8月28日語言理論中的不可判定問題定理5.2ETM是不可判定的。

先用標(biāo)準(zhǔn)術(shù)語來寫在證明思路中描述的那個(gè)修改型機(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)行比較，就可確定它們是否相同。ETM={M|M是一個(gè)TM，且L(M)=}空問題10第十頁，共三十頁，2022年，8月28日語言理論中的不可判定問題再假設(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拒絕，則接受。”如果R是ETM的判定器，則S就是ATM的判定器。而ATM

的判定器是不存在的，故ETM

必定是不可判定的。定理5.2ETM是不可判定的。

ETM={M|M是一個(gè)TM，且L(M)=}空問題11第十一頁，共三十頁，2022年，8月28日語言理論中的不可判定問題另一個(gè)與圖靈機(jī)有關(guān)的計(jì)算問題也很有意思，該問題是： 給定一個(gè)圖靈機(jī)和一個(gè)可由某個(gè)更簡單的計(jì)算模型識(shí)別的語言，測定此圖靈機(jī)是否識(shí)別此語言。例如：令REGULARTM是測定一個(gè)給定的圖靈機(jī)是否有一個(gè)與之等價(jià)的有窮自動(dòng)機(jī)問題，則這個(gè)問題與測定一個(gè)給定的圖靈機(jī)是否識(shí)別一個(gè)正則語言的問題相同。

REGULARTM={<M>|M是一個(gè)TM，且L(M)是一個(gè)正則語言}REGULARTM是不可判定的。（定理5.3）檢查關(guān)于語言的任何一個(gè)性質(zhì)是否可由圖靈機(jī)識(shí)別都是不可判定的。（萊斯定理）12第十二頁，共三十頁，2022年，8月28日語言理論中的不可判定問題定理5.4EQTM是不可判定的。

將ETM歸約到EQTM

。設(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也是不可判定的。EQTM={M1,M2|M1和M2都是TM，且L(M1)=L(M2)}13第十三頁，共三十頁，2022年，8月28日利用歷史計(jì)算歸約定義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上的一個(gè)拒絕計(jì)算歷史可類似定義，只是Cl應(yīng)是一個(gè)拒絕格局。計(jì)算歷史都是有限序列。如果M在w上不停機(jī)，則二者不存在。確定型圖靈機(jī)最多只一個(gè)計(jì)算歷史。非確定型圖靈機(jī)可能有多個(gè)計(jì)算歷史。14第十四頁，共三十頁，2022年，8月28日定義5.6

線性界限自動(dòng)機(jī)是一種受到限制的圖靈機(jī)，它不允許其讀寫頭離開包含輸入的帶區(qū)域。如果此機(jī)器試圖將它的讀寫頭移出輸入的兩個(gè)端點(diǎn)，則讀寫頭就保持在原地不動(dòng)。這與普通圖靈機(jī)的讀寫頭不會(huì)離開帶子的左端點(diǎn)的方式一樣。利用歷史計(jì)算歸約的例子定義5.6ababa控制器15第十五頁，共三十頁，2022年，8月28日定義5.6設(shè)M是有q個(gè)狀態(tài)和g個(gè)帶符號(hào)的LBA。對(duì)于長度為n的帶子，M恰有qngn個(gè)不同的格局。線性界限自動(dòng)機(jī)引理5.7

M的格局就像計(jì)算中間的一快照。格局由控制狀態(tài)、讀寫頭位置和帶內(nèi)容組成。這里，M有q

個(gè)狀態(tài)。它的帶長度是n，所以讀寫頭可能處于n個(gè)位置之一，且gn

多個(gè)帶符號(hào)串可能出現(xiàn)在帶上。此三個(gè)量的乘積就是帶長為n的M的格局總數(shù)。

16第十六頁，共三十頁，2022年，8月28日定義5.6ALBA是可判定的。

線性界限自動(dòng)機(jī)的可判定問題定理5.8L=“對(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)。這就是算法為什么在此情形下拒絕的原因。17第十七頁，共三十頁，2022年，8月28日ELBA是不可判定的。

ALLCFG={<G>|G是一個(gè)CFG且L(G)=*}是不可判定的。線性界限自動(dòng)機(jī)的可判定問題18第十八頁，共三十頁，2022年，8月28日主要內(nèi)容5.1語言理論中的不可判定問題5.2一個(gè)簡單的不可判定問題(自學(xué))5.3映射可歸約性

5.3.1可計(jì)算函數(shù)

5.3.2映射可歸約性的形式定義19第十九頁，共三十頁，2022年，8月28日主要內(nèi)容5.1語言理論中的不可判定問題5.2一個(gè)簡單的不可判定問題5.3映射可歸約性

5.3.1可計(jì)算函數(shù)

5.3.2映射可歸約性的形式定義

20第二十頁，共三十頁，2022年，8月28日映射可歸約性將一個(gè)問題歸約為另一個(gè)問題的概念可以用多種方式來形式定義，選擇使用哪種方式要根據(jù)具體應(yīng)用情況。我們的選擇是一種簡單方式的可歸約性，叫做映射可歸約性。粗略地說，“用映射可歸約性將問題A歸約為問題B”是指，存在一個(gè)可計(jì)算函數(shù)，它將問題

A的實(shí)例轉(zhuǎn)換成問題B的實(shí)例。如果有了這樣一個(gè)轉(zhuǎn)換函數(shù)，就能用B的解決方案來解。原因是，A的任何一個(gè)實(shí)例可以這樣來解：首先用這個(gè)歸約將A轉(zhuǎn)換為B的一個(gè)實(shí)例，然后應(yīng)用B的解決方案。21第二十一頁，共三十頁，2022年，8月28日例5.13整數(shù)上所有通常的算術(shù)運(yùn)算都是可計(jì)算函數(shù)。例如，可以制造一個(gè)機(jī)器，它以<m,n>為輸入且返回m與n的和m+n。定義5.6函數(shù)f:

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

可計(jì)算函數(shù)定義5.1222第二十二頁，共三十頁，2022年，8月28日可計(jì)算函數(shù)例5.14可計(jì)算函數(shù)可以是機(jī)器的描述之間的變換。例如，如果w=<M>是圖靈機(jī)的編碼，可以有一個(gè)可計(jì)算函數(shù)f，以w

為輸入，且返回一個(gè)圖靈機(jī)的描述<M>。

M是一個(gè)與M識(shí)別相同語言的機(jī)器，但M從不試圖將它的讀寫頭移出它的帶的左端點(diǎn)。函數(shù)f通過在M的描述中加入一些狀態(tài)來完成這個(gè)任務(wù)。如果M不是圖靈機(jī)的合法編碼，f就返回

23第二十三頁，共三十頁，2022年，8月28日定義5.6語言A是映射可歸約到語言B的，如果存在可計(jì)算函數(shù)f

:**使得對(duì)每個(gè)w，

w∈A

f(w)∈B記作A≤mB。稱函數(shù)f為A到B的歸約。映射可歸約性的形式化定義定義5.15ABff24第二十四頁，共三十頁，2022年，8月28日定義5.6如果A≤mB且B是可判定的，則A也是可判定的。映射可歸約性定理5.16設(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)行如所求。定義5.6如果A≤mB且A是不可判定的，則B也是不可判定的。

推論5.1725第二十五頁，共三十頁，2022年，8月28日例5.8定理5.1使用從ATM出發(fā)的一個(gè)，證明了HALTTM是不可判定。這個(gè)歸約說明了怎么用HALTTM的判定器給出ATM的判定器。以下展示從ATM到HALTTM的映射可歸約性。必須提供一個(gè)可計(jì)算函數(shù)f，它使用形如<M,w>的輸入，返回形如<M,w>的輸出，使得<M,w>∈ATM當(dāng)且僅當(dāng)<M,w>∈HALTTM

下面的機(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>?！?6第二十六頁，共三十頁，20