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

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

可歸約到B）如果B

是可判定的，則A

也是可判定的。如果A

是不可判定的，則B

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

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

）假設(shè)TM

R

判定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)。這樣，如果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

>上運(yùn)行TM

R。如果R

拒絕，則拒絕。如果R

接受，則在w

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

判定HALTTM，則S

判定ATM。因?yàn)锳TM

是不可判定的，故HALTTM

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

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

可由TM

Mp判定使用Mp

來判定Q:對(duì)Q

的每個(gè)實(shí)例IQ,構(gòu)造P的實(shí)例IP使用Mp判定IP由第3.2步的判定結(jié)果得到對(duì)Iq的判定因?yàn)镼已知的不可判定,所以MP不可能存在.9語言理論中的不可判定問題定理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)=?

}

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

是不可判定的。先用標(biāo)準(zhǔn)術(shù)語來寫在證明思路中描述的那個(gè)修改型機(jī)器M1.M1

=“在輸入x上：如果x≠w，則拒絕。如果x=w，則在x上運(yùn)行M，當(dāng)M接受時(shí)，就接受?！边@個(gè)機(jī)器以w作為它的描述的一部分。檢查x=w是否成立的方法很顯然，即掃描輸入并用一個(gè)字符一個(gè)字符地將它與w

進(jìn)行比較，就可確定它們是否相同。M1為非空當(dāng)且僅當(dāng)M接受w。ETM

=

{<M>

|

M

是一個(gè)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

>上運(yùn)行R。如果R接受，則拒絕；如果R拒絕，則接受。”如果R

是ETM

的判定器，則S

就是ATM

的判定器。而ATM

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

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

是不可判定的。ETM

=

{<M>

|

M

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

}

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

歸約到EQTM

。設(shè)TM

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

的TM

S：S=“對(duì)于輸入<M>，其中M

是TM：在輸入<M,

M1>上運(yùn)行R，其中M1

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

判定EQTM，則S

判定ETM。但由定理5.2，ETM

是不可判定的，故EQTM

也是不可判定的。EQTM

={<M1,M2>|

M1

和M2

都是TM，且L(M1)=L(M2)}語言理論中的不可判定問題13另一個(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）語言理論中的不可判定問題14REGULARTM是不可判定的。（定理5.3）即對(duì)于一個(gè)給定的圖靈機(jī)TM，判斷其是否存在一個(gè)等價(jià)的DFA。證明思想：將ATM歸約到REGULARTM。假定圖靈機(jī)TM

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

到

REGULAR

TMATM

的判定器TM

S

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

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

是一個(gè)TM，w

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

M1

如下:M1

=“輸入為x:若x

=0n1n

，n

?0，則接受;若

x

?

0n1n,

在

w上運(yùn)行M，M1接受x當(dāng)且僅當(dāng)

M

接受w.”在<M1>上運(yùn)行R.若R接受<M1>，