計算理論導引第4章 可判定性

1計算理論第4章可判定性2主要內容4.1可判定語言

4.1.1與正則語言相關的可判定問題

4.1.2與上下文無關語言相關的可判定問題4.2停機問題

4.2.1對角化方法

4.2.2停機問題是不可判定的

4.2.3一個圖靈不可識別語言與正則語言相關的可判定問題定理4.1ADFA是一個可判定語言。設計一個判定ADFA的TMM。M=“對于輸入<B,w>，其中B

是DFA，w

是串： 1)在輸入w上模擬B。

2)如果模擬以接受狀態(tài)結束，則接受；

如果以非接受狀態(tài)結束，則拒絕。”ADFA={<B,w>|B

是DFA，w是串，B接受w

}ADFA是一個可判定語言Step1:

檢查輸入<B,w>，它表示輸入串w和DFAB。

B

的一個合理的表示方法是簡單的列出它的五個元素Q,

,,q0

及F。當M

收到輸入時，首先檢查它是否正確的表示了DFAB

和串w。如果不是，則拒絕Step2:

M

直接執(zhí)行模擬。用在帶上寫下信息的方法，它可以跟蹤B

在輸入M上運行時的當前狀態(tài)和當前位置。 運行開始時，B

的當前狀態(tài)時q0，讀寫頭的當前位置是w的最左端符號。狀態(tài)和位置的更新是由轉移函數(shù)決定的。 當M

處理完w的最后一個符號時，如果B處于接收狀態(tài)，則M

接受這個輸入；如果不是，則M拒絕。與正則語言相關的可判定問題定理4.2ANFA是一個可判定語言。構造一個判定ANFA的TMN。用M

作為N

的子程序。N=“對于輸入<B,w>，其中B是NFA，w

是串： 1)將NFAB轉換成一個等價的DFAC。 2)在輸入

<C,w>上運行TMM。 3)如果M

接受，則接受，否則拒絕。”ANFA={<B,w>|B

是NFA，w是串，B接受w

}與正則語言相關的可判定問題定理4.3AREX是一個可判定語言。P=“對于輸入<R,w>上，其中R是正則表達式，w是串： 1)將正則表達式R

轉換成一個等價的NFAA。 2)在輸入

<A,w>上運行TMM。 3)如果N

接受，則接受，否則拒絕?！盇REX={<R,w>|R是正則表達式，w是串，R派生w}有窮自動機的空性質測試定理4.4EDFA是一個可判定語言。EDFA={<A>|A

是DFA，且L(A)=

}T=“對于輸入<A>，其中A

是DFA：1)標記A

的起始狀態(tài)。2)重復下列步驟，直至所有狀態(tài)都被標記。3)對于一個狀態(tài)，如果有一個到達它的轉移是從某個已經(jīng)標記過的狀態(tài)出發(fā)的，則將其標記。4)如果沒有接受狀態(tài)被標記，則接受，否則拒絕?！迸c正則語言相關的可判定問題定理4.5EQDFA是一個可判定語言。EQDFA={<A,B>|A

和B

都是DFA，且L(A)=L(B)

}構造DFAC，使得L(C)=(L(A)∩~L(B))∪(~L(A)∩L(B))L(C)=

當且僅當L(A)=L(B)

F=“對于輸入<A,B>，其中A

和B

都是DFA：1)構造DFAC。2)再輸入<C>上運行定理4.4中的TMT。3)如果T接受，則接受，否則拒絕?！迸c上下文無關語言相關的可判定問題定理4.6ACFG是一個可判定語言。ACFG={<G,w>|G

是CFG，w是串，G派生w

}如果G

是喬姆斯基范式，w的任意派生都是2n-1步，其中n是w

的長度。（見書上的問題2.26）S=“對于輸入<G,w>上，其中R是一個CFG，w是串：1)將G轉換成與之等價的喬姆斯基文法。2)列出所有2n-1步的派生，其中n是w的長度，除非n=0，此時列出一部步以內的派生。3)如果這些派生中有一個產(chǎn)生w，則接受，否則拒絕?！迸c上下文無關語言相關的可判定問題定理4.7ECFG是一個可判定語言。ECFG={<G>|G

是CFG，且L(A)=

}要點：檢查每一個變元，以確定該變元能否產(chǎn)生終極符。R=“對于輸入<G>上，其中G是一個CFG：1)將G

中所有的終結符都作上標記。2)重復下列步驟，直至找不到可以作標記的變元。3)如果G

有規(guī)則A

U1U2…UK，且U1,U2,…,UK中的每個符號都已被作過標記，則將變元A

作標記。4)如果起始變元沒有被標記，則接受，否則拒絕。”與上下文無關語言相關的可判定問題定理4.8每個上下文無關語言都是可判定的。設G

是A

的一個CFG。設計一個判定A

的TMMG，它在自己內部建立G

的一個備份。其工作方式如下：MG=“對于輸入w:1)在輸入<G,w>上運行TMS。2)如果該機器接收，則接受；否則拒絕?！迸c上下文無關語言相關的不可判定問題EQCFG={<G,H>|G

和H

是CFG，且L(G)=L(H)

}四個語言類正則的上下文無關的可判定的圖靈可識別的14主要內容4.1可判定語言

4.1.1與正則語言相關的可判定問題

4.1.2與上下文無關語言相關的可判定問題4.2停機問題

4.2.1對角化方法

4.2.2停機問題是不可判定的

4.2.3一個圖靈不可識別語言停機問題定理4.9ATM是不可判定的。ATM={<M,w>|M

是一個TM，且接受w

}U=“對于輸入<M,w>上，其中M

是一個TM，w是串：1)在輸入w上模擬M。2)如果M

進入接受狀態(tài)，則接受；如果M

進入拒絕狀態(tài)，則拒絕?！比绻鸐

在w

上循環(huán)，則機器U

在輸入<M,w>上循環(huán)。因此，U不能判定ATM。對角化方法定義4.10設A

和B

是兩個集合，f是從A到B

的函數(shù)。如果f從不將兩個不同元素映射到同一個對象，即：只要a≠b就有f(a)≠f(b)，則稱f是一對一映射的。如果f

能擊中B的每個元素，即：對B的每個元素b，都存在aA，使得f(a)=b，則稱f是滿映射。如果存在函數(shù)f：AB，f是一對一映射又是滿映射，則稱集合A和B有相同規(guī)模。而既是一對一映射又是滿映射的函數(shù)稱為對應。在對應中，A的每個元素映射到B的唯一一個元素，且B的每個元素都有A的唯一一個元素映射到它。對應就是將A的元素與B的元素進行配對的方法。自然數(shù)集合和偶數(shù)集合17例4.11

設N是自然數(shù)集合{1,2,3,…}，

是偶自然數(shù)集合

{2,4,6,…}。用康托的關于進和規(guī)模的定義可以看到：N和

有相同的規(guī)模。 從N映射到

的對應f是f(n)=2n?？蓴?shù)集合定義4.12如果一個集合A是有限的或者與N有相同的規(guī)模，則A是可數(shù)的。有理數(shù)集合和自然數(shù)集合例4.13

設Q={m/n

|m,nN}是正有理數(shù)集合，Q和N的規(guī)模相同。對角化方法還是有—些集合，因為它們太大了，故沒有與N的對應。這樣的集合稱為不可數(shù)的。實數(shù)集是一個不可數(shù)集合的例子。實數(shù)是用十進制表示的數(shù)。數(shù)n＝3.1415926…和√2＝1.414235…都是實數(shù)。設R是實數(shù)集合?？低凶C明了R是不可數(shù)的。下面用對角線方法證明之。對角化方法定理4.14R是不可數(shù)的。證明：假設在R與N間存在著對應f，現(xiàn)在的任務是證明它沒有應有的性質。因為它是一個對應，必須能將N的所有元素與R的所有元素進行配對。如果能找到R中的一個x，它和N中的任何元素都不能配對，則找到矛盾。

為此，實際構造出這樣一個x。方法為：在選擇它的每一位數(shù)時，都使得x不同于某個實數(shù)，且此實數(shù)已與N中的一個元素配對。這樣就能保證x不同于任何已配對的實數(shù)。對角化方法用一個例子來說明這個思路。假設對應f存在，且設f(1)=3.14159…，f(2)=55.55555…，f(3)=…等等。則f將自然數(shù)1與3.14159…配對，將2與55.55555…配對，依此類推。表4-2給出了此假定存在的f的一些值，f聯(lián)系了N和R。只要給出x的十進制表示，則x就可以構造出來。所構造的x是在0與1之間的一個數(shù)，所以重要的是小數(shù)點后面的數(shù)字。要保證對每個n都有x

≠f(n)。為保證x

≠f(1)，只要保證x的第一位小數(shù)不同于f(1)＝3.14159…的第一位小數(shù)，即不定理4.14R是不可數(shù)的。對角化方法是數(shù)字1，隨意地令它為4。為保證x

≠f(2)，只要保證x的第二位小數(shù)不同于f(2)＝55.555555….的第二位小數(shù)。即不是數(shù)字5，任意地令它為6。f(3)＝0.12345…的第三個小數(shù)是3，故可取x的第三位小數(shù)是任一個不為3數(shù)字，比如4。沿著表4-2中的對角線，以這種方法繼續(xù)下去，就能夠得到f的所有數(shù)字。如表4-3所示。不難知道，對任意n，x都不是f(n)，因為x與f(n)在第n個小數(shù)位上不同。定理4.14R是不可數(shù)的。對角化方法上述定理對計算理論有著重要的應用，它表明有些語言是不可判定的．甚至不是圖靈可識別的，原因是：有不可數(shù)個語言，卻只有可數(shù)個圖靈機。由于一個圖靈機只能識別一個語言，而語言比圖靈機更多，故有些語言不能用任何的圖靈機識別。這樣的語言就不是圖靈可識別的，正如下面推論所說。定理4.14R是不可數(shù)的。對角化方法推論4.15存在不能被任何圖靈可識別的語言。證明：為證明所有圖靈機構成的集合是可數(shù)的，首先證明：對仟意的字母表

，其上所有串的集合*是可數(shù)的。這是因為，對每個自然數(shù)n，長度為n的串只有有限多個，我們先寫下長度為0的所有串，再寫下長度為1的所有串。再寫下長度為2的所有串，依此類推，這樣就能構造出

的序列。由所有圖靈機構成的集合是可數(shù)的，原因是：每個圖靈機有一個編碼．它是一個串＜M＞。只要去掉那些不是圖靈機合法編碼的串，就得到了所有圖靈機的序列。

對角化方法為證明由所有語言構成的集合是不可數(shù)的，首先證明由所有無限二進制序列構成的集合是不可數(shù)的。所謂的無限二進制序列是指由0或l構成的無限序列。以β記所有無限二進制序列構成的集合，可以通過對角化方法來證明β是不可數(shù)的。此法類似于定理4.14所用的方法，只不過那時是證明R是個可數(shù)的。

設?是字母表

所有語言的集合。只要給出?與

的一個對應，就證明了此這兩個集合有相同的規(guī)模，也就證明?是不可數(shù)的。設*={s1，s2，s3，….}。每個語言A∈?在β中都推論4.15存在不能被任何圖靈可識別的語言。對角化方法有唯一的一個相應序列：如果si∈A，則此序列的第i位為1，如果si

∈（錯）A，則此序列的第i位為0。此序列被稱為A的特征序列。例如，如果A是字母表{0，1}上以0開始的串構成的語言，則其特征序列XA是：*={，0，1，00，01，10，11，000，001，….}A={

0，00，01，10000，001，….}

XA=010110011….令函數(shù)集：?

β為；f(A)是A的特征序列，則f是一對一且滿射的，即是一個對應。因為β是不可數(shù)的，故?也是不可數(shù)的。

推論4.15存在不能被任何圖靈可識別的語言。停機問題是不可判定的定理4.9ATM是不可判定的。ATM={<M,w>|M

是一個TM，且接受w

}ATM是可識別的。U=“對于輸入<M,w>上，其中M

是一個TM，w是串：1)在輸入w上模擬M。2)如果M

進入接受狀態(tài)，則接受； 如果M

進入拒絕狀態(tài)，則拒絕?！比绻鸐

在w

上循環(huán)，則機器U

在輸入<M,w>上循環(huán)。因此，U不能判定ATM。29停機問題是不可判定的現(xiàn)在證明下列語言的不可判定性：

ATM＝{<M,w>|M是一個TM，且M接受w}假沒ATM是可判定的，下面將由之導出矛盾。設H是ATM的判定器。令M是一個TM，w是一個串。在輸入<M,w>上，如果M接受w，則H就停機且接受w；如果M不接受w，則H也會停機，但拒絕w。換句話說，H是一個TM使得：30停機問題是不可判定的現(xiàn)在來構造一個新的圖靈機D，它以H作為了程序。當M被輸入它自己的描述＜M＞時，TMD就調用H，以了解M將做什么。一旦得到這個信息，D就反著做，即：如果M接受，它就拒絕；如果M不接受，它就接受。下面是D的描述。D＝“對干輸入<M>，其中M是一個TM：

1)在輸入<M,<M>>上運行H。

2)輸出H輸出的相反結論，即， 如果H接受，就拒絕；如果H拒絕，就接受?！?/p>

31停機問題是不可判定的“在一個機器上運行它自己的描述”類似于以一個程序本身作為輸入來運行這個程序，是有意義的。總而言之，當以D的描述<D>作為輸入來運行D自身時，結果是：

這顯然是一個矛盾。所以，TMD和TMH都不存在。停機問題是不可判定的‘Acceptancebehavior’ofMion

Mj

圖靈機輸入串停機問題是不可判定的‘Decidingbehavior’ofGon

Mi,Mj

，擬用對角線上反碼構造圖靈機D停機問題是不可判定的DisagreeingDhastooccurinlistaswell…D也是一切合乎條件的TM中的一個，所以也在其中，下頁相反相反相反相反停機問題是不可判定的相反相反相反相反ContradictionforDoninputD.接受、拒絕都矛盾？一個圖靈不可識別語言ATM是一個不可判定的語言。但它是圖靈可識別的?，F(xiàn)在介紹另一個語言，此語言甚至是不可識別的。可以證明：如果一個語言和它的補都是圖靈可識別的，則此語言也是可判定的。這樣，對任何不可判定語言，它或它的補至少有一個不是圖靈可識別的。一個語言的補是由不在此語言中的所有串構成的語言。如果一個語言是一個圖靈可識別語言的補集，則稱它是補圖靈可識別的(co-TMrecognizable

)。一個圖靈不可識別語言定理4.16一個語言是可判定的，當且僅當它既是圖靈可識別的，也是補圖靈可識別的。

如果A是可判定的，很容易看出A和它的補ā都是圖靈可識別的，因為任何可判定語言都是圖靈可識別的，且任何可判定語言的補也是可判定的。

如果A和ā都是圖靈可識別的， 令M1是A的識別器，M2是ā的識別器。 下列圖靈機M是A的判定：

M＝“對于輸入w：

1)在輸入w

上并行運行M1

和M2。

2)如果