計算理論導(dǎo)引w11不可判定性及證明

計算理論1前言2本章討論另外幾個不可解的問題。在討論過程中，將介紹一個基本方法，可用來證明問題是計算上不可解的，這個方法稱為可歸約性。歸約旨在將一個問題轉(zhuǎn)化為加一個問題，且使得可以用第二個問題的解來解第一個問題，在日常生活中，雖然不這樣稱呼，但時常會遇見可歸約性問題。例如，在一個新城市中認路，如果有一張地圖，事情就容易了。這樣，就將在城市認路問題歸約為得到地圖問題。3前言可歸約性總是涉及兩個問題，稱之為A和B。如果A可歸約到B，就可用B

的解來解A?？蓺w約性說的不是怎樣去解A或B，而是在知道B的解時怎么去解A。歸約的目的在于：將一個問題轉(zhuǎn)化為另一個問題；且用第二個問題的解來解第一個問題。歸約的應(yīng)用（A

可歸約到B）如果B

是可判定的，則A

也是可判定的。如果A

是不可判定的，則B

也是不可判定的。主要內(nèi)容4語言理論中的不可判定問題一個簡單的不可判定問題（自學(xué)）映射可歸約性可計算函數(shù)映射可歸約性的形式定義語言理論中的不可判定問題5ATM={<M,w>|

M

是一個TM，且接受w

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

的形式化描述HALTTM

={<M,w>|

M是一個TM,且對輸入w

停機}HALTTM

是不可判定的定理5.16HALTTM是不可判定的。證明思路：反證法。（將ATM歸約到HALTTM

）假設(shè)TM

R

判定HALTTM，利用R

可以構(gòu)造一個判定ATM

的TMS。使用R，可以檢查M

對w

是否停機，如果M

對w

不停機，S

就拒絕，因為<M,w

>不在ATM

中。

如果M對w確實停機，S就模擬它，而不會有死循環(huán)的危險。這樣，如果TM

R

存在，就能判定ATM。語言理論中的不可判定問題定理5.17HALTTM是不可判定的。假設(shè)TM

R

判定HALTTM，由之可以構(gòu)造TM

S

來判定ATM，其構(gòu)造如下：S=“

在輸入<M,w

>上，此處<M,

w

>是TM

M

和串w

的編碼：在輸入<M,

w

>上運行TM

R。如果R

拒絕，則拒絕。如果R

接受，則在w

上模擬M，直到它停機。如果M已經(jīng)接受，則接受；如果M已經(jīng)拒絕，則拒絕?！憋@然，如果R

判定HALTTM，則S

判定ATM。因為ATM

是不可判定的，故HALTTM

也必定是不可判定的。歸約方法總結(jié)：用歸約證明問題P

的不可判定性的步驟:找一個已知的不可判定問題Q;假定P

可由TM

Mp判定使用Mp

來判定Q:對Q

的每個實例IQ,構(gòu)造P的實例IP使用Mp判定IP由第3.2步的判定結(jié)果得到對Iq的判定因為Q已知的不可判定,所以MP不可能存在.9語言理論中的不可判定問題定理5.2ETM

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

是可判定的，以此證明ATM

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

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

的S。當S

收到輸入<M,

w>時，如何運行？構(gòu)造S

的一個想法是：輸入<M>上運行R，看它是否接受：如果接受，則L(M)是空集，因此M不接受w。如果R拒絕w，則只知道L(M)不空，即M接受某個串，但是不知道是否接受這個特定的w。因此，不能在<M>

上運行R。目標：修改<M>，使得除了w

外，M

對所有串都拒絕。ETM

=

{<M>

|

M

是一個TM，且L(M)=?

}

空問題10語言理論中的不可判定問題定理5.2ETM

是不可判定的。先用標準術(shù)語來寫在證明思路中描述的那個修改型機器M1.M1

=“在輸入x上：如果x≠w，則拒絕。如果x=w，則在x上運行M，當M接受時，就接受。”這個機器以w作為它的描述的一部分。檢查x=w是否成立的方法很顯然，即掃描輸入并用一個字符一個字符地將它與w

進行比較，就可確定它們是否相同。M1為非空當且僅當M接受w。ETM

=

{<M>

|

M

是一個TM，且L(M)=?

}

空問題語言理論中的不可判定問題再假設(shè)TM

R

判定ETM。如下構(gòu)造判定ATM

的TM

S:S=“在輸入<M,

w

>上，此處<M,w

>是TM

M

和串w

的編碼：用M

和w

的描述來構(gòu)造上述TM

M1。在輸入<M1

>上運行R。如果R接受，則拒絕；如果R拒絕，則接受?！比绻鸕

是ETM

的判定器，則S

就是ATM

的判定器。而ATM

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

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

是不可判定的。ETM

=

{<M>

|

M

是一個TM，且L(M)=?

}

空問題語言理論中的不可判定問題定理5.412EQTM是不可判定的。將ETM

歸約到EQTM

。設(shè)TM

R判定EQTM。如下構(gòu)造判定ETM

的TM

S：S=“對于輸入<M>，其中M

是TM：在輸入<M,

M1>上運行R，其中M1

是拒絕所有輸入的圖靈機。如果R接受，則接受；如果R拒絕，則拒絕。如果R

判定EQTM，則S

判定ETM。但由定理5.2，ETM

是不可判定的，故EQTM

也是不可判定的。EQTM

={<M1,M2>|

M1

和M2

都是TM，且L(M1)=L(M2)}語言理論中的不可判定問題13另一個與圖靈機有關(guān)的計算問題也很有意思，該問題是：給定一個圖靈機和一個可由某個更簡單的計算模型識別的語言，測定此圖靈機是否識別此語言。例如：令REGULARTM是測定一個給定的圖靈機是否有一個與之等價的有窮自動機問題，則這個問題與測定一個給定的圖靈機是否識別一個正則語言的問題相同。REGULARTM

={<M>

|

M

是一個TM，且L(M)是一個正則語言}REGULARTM

是不可判定的。（定理5.3）語言理論中的不可判定問題14REGULARTM是不可判定的。（定理5.3）即對于一個給定的圖靈機TM，判斷其是否存在一個等價的DFA。證明思想：將ATM歸約到REGULARTM。假定圖靈機TM

R是REGULARTM的判定器；使用R構(gòu)造出ATM的判定器S，構(gòu)造一個圖靈機M1，使得L(M1)為正則語言當且僅當M接受w.從ATM

到

REGULAR

TMATM

的判定器TM

S

的構(gòu)造如下：S

=“輸入為<M,w>,M

是一個TM，w

是字符串:構(gòu)造TM

M1

如下:M1

=“輸入為x:若x

=0n1n

，n

?0，則接受;若

x

?

0n1n,

在

w上運行M，M1接受x當且僅當

M

接受w.”在<M1>上運行R.若R接受<M1>，