第七章圖靈機(jī)

第七章圖靈機(jī)周俊萍zhoujp877@本章，我們將介紹圖靈機(jī)－計(jì)算機(jī)的一種簡單數(shù)學(xué)模型。盡管圖靈機(jī)簡單，但它具有模擬通用計(jì)算機(jī)計(jì)算的能力。人們研究圖靈機(jī)不僅是為了研究它所定義的語言類（稱為遞歸可枚舉集合）。也是為了研究它所計(jì)算的整數(shù)函數(shù)類（稱為部分遞歸函數(shù)）。還將引用其它各種計(jì)算模型，它們在計(jì)算表達(dá)能力上都等價(jià)于圖靈機(jī)。圖靈機(jī)是這樣一種有限狀態(tài)機(jī)，在每次狀態(tài)轉(zhuǎn)移的時(shí)候在帶上面打印一個符號，帶頭可以雙向運(yùn)動，從而允許圖靈機(jī)能夠按照要求的次數(shù)讀取以及操作作為作為輸入，圖靈機(jī)的帶有一個左邊界，并且能夠向右無限擴(kuò)展。7.2圖靈機(jī)模型有效過程的形式模型應(yīng)該具有某些性質(zhì)，首先，每個過程都應(yīng)該是有窮可描述的。其次，過程應(yīng)該由離散的步組成，每一步能夠機(jī)械地被執(zhí)行。A.Turing在1936年介紹了這樣一個模型-圖靈機(jī)。這里我們介紹它的一種變形。a1a2…ai…anBB…有限控制器圖7.1基本圖靈機(jī)圖7.1說明的基本模型有一個有限控制器，一條輸入帶和一個帶頭，帶被分成許多單元，帶頭在每一時(shí)刻掃視帶上的一個單元。該帶有一個最左單元，向右則是無限的，帶的每個單元正好可容納有窮個帶符號中的一個，開始時(shí)，最左邊n個單元對于某個有窮數(shù)n0裝著輸入，它是一個字符串，符號都是選自帶符號的一個子集，即所謂輸入符號集合，余下的無窮多個單元都存放空白符（它是一個特殊的帶符號，但不是輸入符號）。在一個動作中，圖靈機(jī)根據(jù)帶頭掃視的符號和有限控制器的狀態(tài)。1改變狀態(tài)；2在被掃視的帶單元上打印一個符號，以代替原來寫在這里的符號；3將帶頭向左或右移一個單元。形式上,一個圖靈機(jī)(TM)被記作:M＝(Q,,,,q0,B,F)這里Q是狀態(tài)的有窮集合；是所允許的帶符號的有窮集合；B是的一個符號，即空白符；是的一個不包含B的子集，即輸入符號集合；是次動作函數(shù)，是一個從Q到Q（L，R）的映射（然而，可以對某些自變量沒有意義）;q0在Q中，是初始狀態(tài)；FQ是終結(jié)狀態(tài)集合。我們用a1qa2來標(biāo)記圖靈機(jī)M的一個瞬時(shí)描述（ID），其中，q在Q中，是M的當(dāng)前狀態(tài)。a1a2是*中的字符串，它或是一直到最右非空白符號為止的帶上的內(nèi)容，或是一直到帶頭左邊符號為止的帶上的內(nèi)容。我們定義M的一個動作如下。設(shè)X1X2．．．Xi-1qXi．．．Xn是一個ID。假定（q,Xi）＝（P,Y,L），這里如果i-1=n，那么Xi取為B。如果i=1，那么就沒有下一個ID，因?yàn)閹ь^不允許落在帶左端的外面，如果i>1，那么我們寫出X1X2…Xi-1qXi…Xn?MX1X2…Xi-1pYXi+1…Xn(7．1)另一方面，假定（q,Xi）＝（P,Y,R），那么我們寫出X1X2…Xi-1qXi…Xn?MX1X2…Xi-1YPXi+1…Xn(7．2)注意，在i-1=n情況下，字符串XiXn是空的，上式的右邊要比左邊長。如果把兩個ID用?M連接起來，我們就說，第二個ID是通過一個動作從第一個ID產(chǎn)生的.如果一個ID是通過有限個動作（包括零個動作）從另一個產(chǎn)生的，那么它們可用符號?*M連結(jié)起來。在不起混淆時(shí)，我們可以從?M和?*M中省掉下標(biāo)M。被M接受（識別）的語言記作L（M），它是＊中那樣一些字的集合，當(dāng)這些字被放在M的帶上，M處于狀態(tài)q0且M的帶頭處在最左單元上時(shí)，這些字將使M進(jìn)入一個終結(jié)狀態(tài)。

形式上,被M＝(Q,,,,q0,B,

F）接受的語言是：｛在*中,且對于F中某個p,*中某個a1和a2,q0

?*a1pa2｝給定一個識別語言L的TM，不失一般性，我們假定，當(dāng)輸入被接受時(shí)，TM將停止，也就是說，沒有下一個動作，然而，對于不被接受的字，TM可能永不停止。例7.1接受語言L＝{0n1nn1｝的TM

M的設(shè)計(jì)如下:起初，M的帶包含0n1n，后面跟著無窮多個空白符，用X替換M最左邊的0，右移至最左邊的1，用Y替換它，左移去尋找最右邊的X，然后右移一個單元到最左邊的0，重復(fù)這個循環(huán)。但是，若在搜索1時(shí)，M找到了一個空白符，那么M停止而不接受，若在將一個1改變成Y后，M再也找不到0了，那么M檢查一下是否還剩1，如果沒有，M接受。設(shè)Q={q0,q1,q2,q3,q4}，={0,1,X,y,B}，而F={q4}，非形式地，每個狀態(tài)都表示程序中的一個語句或一組語句。狀態(tài)q0在開始時(shí)被進(jìn)入，又恰好在每次用X替換一個最左的0之前被進(jìn)入，用狀態(tài)q1向右搜索，跳過所有的0和Y，直到發(fā)現(xiàn)最左的1。如果M找到一個1，M就將它變?yōu)閅，同時(shí)進(jìn)入狀態(tài)q2。狀態(tài)q2向左搜索X，剛一找到X，就進(jìn)入狀態(tài)q0，當(dāng)它改變狀態(tài)時(shí)，右移到最左的0。當(dāng)M在狀態(tài)q2中向右搜索時(shí)，若在一個1之前遇到一個B或X，則輸入被拒絕，這或者是有太多的0，或者輸入不是在0*1*中。具體次動作函數(shù)設(shè)計(jì)如下圖7.2

狀態(tài)符號

0

1

X

Y

B

q0(q1,X,R)--(q3,Y,R)-q1(q1,0,R)(q2,Y,L)-(q1,Y,R)-q2(q2,0,L)-(q0,X,R)(q2,Y,L)-q3---(q3,Y,R)(q4,B,R)q4-----圖7.2函數(shù)q00011?Xq1011?X0q111?Xq20Y1?

q2X0Y1?Xq00Y1?XXq1Y1?XXYq1?XXq2YY?Xq2XYY?XXq0YY?XXYq3Y?XXYYq3

?XXYYBq4圖7.3M的一個計(jì)算

狀態(tài)q0還有另外一個作用，如果在狀態(tài)q2后找到了最右的X，并且有一個Y就在它的緊右邊，那么0已經(jīng)被耗盡了，掃視Y的同時(shí)，就從q0轉(zhuǎn)入狀態(tài)q3，以便掃過Y并檢查是否再沒有1了。如果Y后面是B，則進(jìn)入狀態(tài)q4，并接受輸入；否則字符串被拒絕。函數(shù)示于圖7.2。圖7.3表示M在輸入0011上的計(jì)算。例如，第一個動作可以用（q,0）＝（q,X,R）這個事實(shí)來解釋；最后一個動作可以用（q,B）＝（q,B,R）這個事實(shí)來解釋；讀者應(yīng)該在某些被拒絕的輸入上模擬M，諸如001101，001和011。本章其余部分主要介紹標(biāo)準(zhǔn)圖靈機(jī)的一些變形，每種變形都從某種程度上7.3圖靈機(jī)的變形把圖靈機(jī)作為計(jì)算的一種通用模型的原因之一就是：我們一直在討論的這一模型等價(jià)于許多修改過的、初看上去似乎有更強(qiáng)的計(jì)算能力的變形。本節(jié)，我們將給出某些等價(jià)定理的非形式證明。一個具有雙向無限帶的圖靈機(jī)，象在原來模型中一樣，仍記作M＝（Q，，，，q0，B，F(xiàn)）。就象其名字所暗示的，帶向左和向右都是無限的。我們象對單向無限TM那樣來標(biāo)記這個裝置的ID。不過，我們想象，在帶上現(xiàn)時(shí)非空部分的左面和右面都有無窮多個空白單元。具有雙向無限帶的圖靈機(jī)和標(biāo)準(zhǔn)圖靈機(jī)模型是完全等價(jià)的，不同之處只是在于雙向無限帶圖靈機(jī)可以兩個方向無限延伸，由于雙向無限帶圖靈機(jī)沒有左邊界，所以輸入字可以放在帶的任意位置，而其余位置均被假定為空白，初始帶頭在輸入字的左端關(guān)系?M關(guān)聯(lián)兩個ID，右邊的ID可以從左邊的ID通過一個動作得到?？梢韵笤瓉砟Ｐ湍菢觼矶x?M

。但下面的情況除外：如果=（q，X）＝（p,Y,L），那么qXa?M

pBYa（在原來模型中，此時(shí)不能作出動作），如果(q,X)=(p,B,R)，那么qXa├Pa（在原來模型中，B將出現(xiàn)在p的左邊）。初始ID是q0。在原來模型中，圖靈機(jī)的帶有一個左端，而現(xiàn)在圖靈機(jī)的帶卻沒有左端，也不會“脫出”左端，故它可以繼續(xù)向左到隨意遠(yuǎn)。象通常一樣，如果右邊這個ID能通過若干個動作由左邊那個ID得出，則關(guān)系?M關(guān)系著這兩個ID。定理7.3.1

L被一個具有雙向無限帶的TM

M2識別，當(dāng)且僅當(dāng)它被一個具有單向無限帶的TMM1識別。證關(guān)于具有雙向無限帶的TMM2模擬一個具有單向無限帶的TMM1的證明是容易的。前者在其帶頭初始位置的左側(cè)單元上做上記號，然后開始模擬后者，若在模擬期間到達(dá)作過記號的單元，模擬結(jié)束而不接受。反過來，設(shè)M2=（Q2,2,2,2,q2,B,F）是一個具有雙向無限帶的TM。我們來構(gòu)造一個TMM1，它模擬M2，且有一條只在右方無限的帶，M1有兩道，一道表示M2開始掃視的帶單元及其右邊所有的單元，另一道在相反的順序下表示開始單元左方的所有單元。M2和M1的帶間關(guān)系示于圖7.4，M2的初始單元的編號為0，右邊單元的編號為1，2，……，左邊單元為－1，－2，…?！瑼-5A-4A-3A-2A-1A0A1A2A3A4A5…(a)…A-5A-4A-3A-2A-1圖7.4(a)M2的帶；(b)M1的帶A0A1A2A3A4A5…A-1A-2A-3A-4A-5…(b)M1帶的第一單元，在下道中包含符號，它指明這是最左單元，M1的有限控制器能夠分辨M2是正在掃視M1上道中的符號，還是其下道中的符號。十分明顯，M1能夠在下面意義下被構(gòu)造出來，以M1模擬M2：當(dāng)M2在其輸入帶頭初始位置右方時(shí)，M1在其上道工作；當(dāng)M2在其初始帶頭位置左方時(shí)M1在其下道工作。但移動方向恰好和M2的移動方向相反。M1的輸入符號是這樣一些符號：下道上為空白符，上道上為M2的一個輸入符號，這樣的符號與M2的相應(yīng)的輸入符號可視為相同。B等同于[B，B]。我們現(xiàn)在給出M1＝（Q1，1，1，1，q1，B，F(xiàn)1）的形式結(jié)構(gòu)。M1的狀態(tài)集Q1是所有形如[q,U]或[q,D]的對象的集合，這里q在Q2｛q1｝中。注意，第二分量指出M1工作在上道（U表示上）還是工作在下道（D表示下）。1中的帶符號是所有形如［X，Y］的對象，這里X和Y都在1中。此外，Y可以是，一個不在2中的符號。1由所有的符號［a,B］組成，這里a在2中。F1是｛［q,U］，［q,D］｜q在F2中｝，我們定義1如下：（1）對于2{B}中每個a，如果2(q2,a)=(q,X,R)，那么1(q1,[a,B])=([q,U],[X,],R)如果M2在第一個動作中向右移，那么M1在下道中打印用以標(biāo)記帶的端點(diǎn)，將其狀態(tài)的第二分量設(shè)置為U，并向右移。M1狀態(tài)的第一分量保存M2的狀態(tài)。在上道上，M1打印符號X，它是M2要打印的符號。（2）對于2{B}中的每個a，如果2(q2，a)=(q,X,L),那么1(q1,[a,B])=([q,D],[X,],R)如果M2在其第一個動作中左移，象在（1）中一樣，M1記錄M2的次狀態(tài)和M2打印的符號，但將其狀態(tài)第二分量設(shè)置為D，并向右移。還是打印在下道，以標(biāo)記帶的左端點(diǎn)。（3）對于1中的每個[X,Y],Y,且A＝L或R，如果2(q,X)=(p,,Z,A),那么1([q,U],[X,Y])=([p,U],[Z,Y],A)M1在上道上模擬M2。（4）對于1中每個[X,Y],Y，如果2(q,Y)=(p,Z,),那么1([q,D],[X,Y])=([p,D],[X,Z],A)這里，如果A?是R，A就是L，如果A?是L，A就是R。M1在其下道上模擬M2。M1帶頭的移動方向與M2的相反。（5）如果2(q,X)=(p,Y,A)，那么1([q,U],[X,])或1([q,D],[X,])=([p,C],[Y,],R)這里，如果A＝R，則C＝U，如果A＝L，則C＝D。在M2初始掃視單元上，M1模擬M2的一個動作。然后M1工作在上道或下道，這取決于M2的移動的方向。在這種情況下，M1永遠(yuǎn)右移。7.3.2多帶圖靈機(jī)K帶圖靈機(jī)是單帶TM的一種直接推廣。這里k2是一個固定數(shù)，每條帶和基本圖靈機(jī)的帶一樣，被分成無窮多個單元格，帶的兩邊是無限的（也可以是單向無限的），有k個讀寫頭，每個讀寫頭掃描一條帶，可以進(jìn)行一下動作：

（1）改變狀態(tài)（2）在其帶頭掃視的單元上，打印一個新符號；（3）獨(dú)立地將每個帶頭向左或向右移動一個單元，或保持不動。讀寫頭的動作由當(dāng)前的狀態(tài)和k個讀寫頭從k條帶上讀取的k個符號決定，其次動作函數(shù)是Qk({L,R})kQ的部分函數(shù)。如圖7.5三帶圖靈機(jī)有限控制器圖7.1基本圖靈機(jī)…a1……a2……a3…開始時(shí)，輸入出現(xiàn)在第一條帶上，其它帶是空的。結(jié)束時(shí)計(jì)算結(jié)果一般也在該帶上。定理7.3.2如果一個語言L被一個多帶圖靈機(jī)接受，它就能被一個單帶圖靈機(jī)接受。證設(shè)L被一個有k條帶的TM

M1接受。我們可以構(gòu)造一個具有2k道的單帶TM

M2，M1的每條帶對應(yīng)兩條道。一條道記錄M1對應(yīng)帶的內(nèi)容，另一道為空白，不過，在M1的對應(yīng)帶頭掃視的符號所在的單元中有一記號。如圖，M2的有限控制器存貯M1的狀態(tài)以及M2帶頭右方的帶頭記號的數(shù)目。帶頭1帶1XA1A2……Am帶頭2帶2XB1B2……Bm帶頭3帶3XC1C2……Cm圖7.6一條帶對三條帶的模擬用單帶圖靈機(jī)模擬k帶圖靈機(jī)的關(guān)鍵是多道技術(shù)，設(shè)M1是一條k帶圖靈機(jī)，要用一臺基本圖靈機(jī)M2來模擬M1，把M2的帶分成2k道，用2道模擬M1的一條帶，其中一道存放著和M1的對應(yīng)帶一樣的內(nèi)容，；另一道除一個單元格放置一個特殊的符號外所有單元格都是空白。符號指明了這條帶讀寫頭的位置。圖7.6給出了用一條帶模擬3條帶的示意圖。為了模擬M1的每一步動作，M2的讀寫頭要從左到右，再從右到左地做一次往復(fù)運(yùn)動，在模擬開始，M2的讀寫頭位于最左的處，讀寫頭右移讀入每個一所關(guān)注的符號，直到右邊不再有為止。這時(shí)M2已經(jīng)知道了M1的k個讀寫頭掃描的符號，從而也知道了M1在這一步要做的動作。M2的讀寫頭向左往回運(yùn)動并模擬這些動作，直到它的左邊不再有為止。M2要記錄讀寫頭右邊的個數(shù)t。讀寫頭向右運(yùn)動時(shí)每越過一個，t減1.當(dāng)t=0時(shí)，停止向右運(yùn)動，讀寫頭每向左運(yùn)動時(shí)，每越過一個，t加1.當(dāng)t=k時(shí)，停止向左運(yùn)動。最后，M2還要改變它記錄的M1的狀態(tài)。這就完成了對M1的一步計(jì)算的模擬。記錄M1的狀態(tài)，讀到的符號以及t都可以用狀態(tài)實(shí)現(xiàn)，M2的狀態(tài)集為QCk{0,1,…,k}，給出M2的詳細(xì)形式描述是一件很大工作量的事情，這里略去。例7.3.1設(shè)計(jì)識別語言L=｛R|在{0,1}*中｝的單帶TM

M。設(shè)計(jì)思想：方法是將帶頭在輸入上移前移后，從兩端檢查符號，并比較它們，具體過程是：讀寫頭從左到右檢查左端第一個符號和右端第一個符號。若相同，則把它們刪去，回到左端。重復(fù)上述動作。讀寫頭如此左右往復(fù)運(yùn)動，如果在刪去右端的符號后已把整個輸入x刪去，則表明xL，停機(jī)在接受狀態(tài)，如果在某次檢查時(shí)發(fā)現(xiàn)左右兩端的符號不相同，或者刪去右端的符號后只剩下一個符號，則表明xL，停機(jī)在非接受狀態(tài)，見狀態(tài)轉(zhuǎn)移圖如下頁。若在狀態(tài)q2下掃描到0或1,則分別轉(zhuǎn)移到q3,q4。q3q5q7q9和q4q6q8q10分別把帶頭移到右端，并檢查右端符號是否是為0和1.

q3q5q7q9q1q2q4q13q6q12q11q8q10B/RB/RB/RB/RB/LB/LB/L0/B1/B0/B1/B0,1/R0,1/R0,1/R0,1/R0,1/L0,1/L若是，則刪去右端的符號，轉(zhuǎn)移到q11,q11q12q13q2把帶頭移到剩余的字的左端，重復(fù)上述過程。若在狀態(tài)q9下掃到1或者在狀態(tài)q10下掃到0，則表明x不是左右對稱的，停機(jī)。若在狀態(tài)q5或q6下掃到空白符，則表明x的長度為奇數(shù)也停機(jī)。q5,q6,q9,q10都不是接受狀態(tài)。若在狀態(tài)q12下掃到空白符B，則表明在刪去右端的這個符號后已把整個x刪去，xL停機(jī)在接受狀態(tài)q12。若在狀態(tài)q2下掃到空白符B（剛開始計(jì)算時(shí)），則表明x=，也有xL，停機(jī)在q2,q2也是接受狀態(tài)。這臺圖靈機(jī)總是停機(jī)的。注意，用單帶機(jī)識別L時(shí)用到的動作數(shù)大約是輸入長度的平方，而用雙帶機(jī)器時(shí)，同輸入長度成正比時(shí)間就足夠了。7.3.3非確定圖靈機(jī)非確定圖靈機(jī)是一個具有一個有限控制器和單獨(dú)一條單向無限帶的裝置。對于一個給定的狀態(tài)和被帶頭掃視的帶符號，機(jī)器對次動作可以有有限個選擇。每個選擇包括一個新狀態(tài)，一個要打印的帶符號和一個帶頭移動方向。注意，非確定TM不允許作這樣的動作，其下一狀態(tài)來自一個選擇，而打印符號和（或）帶頭移動方向卻來自另一個選擇，如果有任何一個動作選擇序列導(dǎo)致一個接受狀態(tài)，那么非確定TM就接受它的輸入。就象有窮自動機(jī)那樣，對圖靈機(jī)增加非確定性并未使這個裝置接受新的語言。實(shí)際上，非確定性與任何介紹過的或?qū)⒁榻B的推廣（例如雙向無窮TM或多帶TM）組合起來，也不會增加額外的能力。定理7.3.3如果L被一個非確定的圖靈機(jī)M1接受，那么L將被某個確定的圖靈機(jī)M2接受。證對于M1的任何狀態(tài)和帶符號，有有限多個關(guān)于次動作的選擇，它們可以用1，2，…加以編號，設(shè)r是對于任何狀態(tài)――帶符號偶來說的最大選擇數(shù)。于是任何有限的選擇序列都可以表成一個由數(shù)字1到r組成的序列，并不是所有這樣的序列都表示一個動作選擇序列，因?yàn)樵谀承┣闆r下，可能只有少于r個的選擇。M2將有三條帶，第一條保存輸入，在第二條上，M2將以一種系統(tǒng)的方式產(chǎn)生數(shù)字1到r的序列。具體地講，先產(chǎn)生短的序列，等長序列則按數(shù)值大小順序產(chǎn)生。對于在帶2上產(chǎn)生的每個序列，M2都把輸入復(fù)制到帶3上，然后在帶上3上模擬M1，同時(shí)使用帶2上的序列來指明M1的各動作。如果M1進(jìn)入一個接受狀態(tài)，M2也將接受，如果存在一個導(dǎo)致接受的選擇序列，那么它終窮會在帶2上產(chǎn)生出來。在模擬時(shí)，M2將會接受。但若M1沒有選擇序列導(dǎo)致接受，M2不會接受。7.3.4多維圖靈機(jī)讓我們考慮圖靈機(jī)的另一種修改――多維圖靈機(jī)，它也不增加額外的能力。這種裝置具有通常的有限控制器，但帶卻由k維（對于某個固定的k）單元陣列組成，這里在所有2k個方向都是無限的。根據(jù)狀態(tài)和所掃視的符號，該裝置改變狀態(tài)，打印一個新符號，在2k個方向之一上移動它的帶頭，即沿著k軸中的一軸，作正向或負(fù)向移動。開始時(shí)，輸入沿著一個軸排列，帶頭在輸入的左端。任何時(shí)刻，在任何一維中，只有有窮多行包含非空白符號，其中每一行只有有窮多個非空白符號。例如，考慮圖7．7(a)中的二維TM的帶格局。仍如圖7．7(a)所示，畫一個關(guān)于非空符號的矩形。該矩形能夠如圖7．7（b）那樣，一行接一行地表示在一條帶上，＊用來分隔各行，第二道可以用來指出二維TM的帶頭位置。定理7.3.4如果L被一個二維TMM2接受，那么L將被一個一維TMM1接受。證M1如圖7．7（b）那樣表示M2的帶。M1還有第二條帶，下面我們將描述它的用途，這些帶都是雙向無窮的，假設(shè)M2做了一個動作，在該動作中，帶頭不會離開已被M1的帶表示好的矩形。BBBa1BBBBBa2a3a4a5Ba6a7a8a9Ba10BBa11a12a13Ba14a15BBa16a17BBB(a)**BBBa1BBB*BBa2a3a4a5B*a6a7a8a9Ba10B*Ba11a12a13Ba14a15*BBa16a17BBB**(b)圖7.7用一維對二維的模擬（a）兩維帶（b）一維模擬如果動作是水平方向的，那么M1打印一個新符號，改變記錄在M1的控制器中的M2狀態(tài)，然后，簡單地將帶頭記錄向左或向右移一個單元。如果動作是垂直方向的M1，就用它的第二帶來統(tǒng)計(jì)它的帶頭位置與其左邊＊之間單元的個數(shù)。