形式語(yǔ)言與自動(dòng)機(jī)：圖靈機(jī)

1、形式語(yǔ)言與自動(dòng)機(jī)Formal Languages and Automata Theory第八章 圖靈機(jī)2第八章 圖靈機(jī)圖靈機(jī)的提出基本概念計(jì)算模型構(gòu)造方法世界上首臺(tái)電子計(jì)算機(jī)-ENIAC于1946年2月誕生于美國(guó)賓夕法尼亞大學(xué)莫爾學(xué)院安裝在一排2.75米高的金屬柜里，占地面積為170平方米左右，總重量30噸。耗電超過174千瓦；電子管平均每隔7分鐘被燒壞一只學(xué)術(shù)界公認(rèn)電子計(jì)算機(jī)的理論和模型是由英國(guó)數(shù)學(xué)家圖靈在此前10年前即1936年發(fā)表的一篇論文“On computable numbers with an application to the entschedungs problem”中奠定基

2、礎(chǔ)的是關(guān)于德國(guó)大數(shù)學(xué)家希爾伯特提出的問題：是否所有數(shù)學(xué)問題都是可解的回答了這個(gè)問題：有些數(shù)學(xué)問題是不可解的，而自動(dòng)計(jì)算機(jī)的理論模型則是在其論文的一個(gè)腳注中“順便”提出來的1966年ACM紀(jì)念電子計(jì)算機(jī)誕生20周年，設(shè)立了圖靈獎(jiǎng)20世紀(jì)初，數(shù)學(xué)家希爾伯特曾計(jì)劃構(gòu)造一個(gè)可以判定所有數(shù)學(xué)命題真假的算法-“希爾伯特綱領(lǐng)”其基礎(chǔ)是19世紀(jì)英國(guó)數(shù)學(xué)家喬治.布爾創(chuàng)立的布爾代數(shù)從構(gòu)造判定所有的關(guān)于整數(shù)的一階謂詞演算公式的真、假的算法入手一階謂詞演算足以表示CFG產(chǎn)生的*中的任何句子，因此，這個(gè)問題相當(dāng)于“判定一個(gè)CFL的補(bǔ)是否為空？”圖靈機(jī)的提出1931年，奧地利25歲的數(shù)理邏輯學(xué)家哥德爾KGdel提出的關(guān)于

3、形式系統(tǒng)的“不完備性定理”中指出，這種形式系統(tǒng)是不存在的，從而宣告了著名的“希爾伯特綱領(lǐng)”的失敗一個(gè)形式系統(tǒng)是不能窮盡所有的數(shù)學(xué)命題的。哥德爾構(gòu)造了一個(gè)關(guān)于整數(shù)謂詞演算公式，在這個(gè)邏輯系統(tǒng)中，既不能否定它，也不能肯定他圖靈機(jī)的提出圖靈的手稿早在哥德爾研究成果的影響下，圖靈從計(jì)算一個(gè)數(shù)的一般過程入手對(duì)計(jì)算的本質(zhì)進(jìn)行了研究所謂計(jì)算就是計(jì)算者人或機(jī)器對(duì)一條兩端可無限延長(zhǎng)的紙帶上的一串0和1執(zhí)行指令，一步一步地改變紙帶上的0或1，經(jīng)過有限步驟，最后得到一個(gè)滿足預(yù)先規(guī)定的符號(hào)串的變換過程。用形式化方法成功表述可計(jì)算這一過程的本質(zhì)。圖靈機(jī)的提出提出目的 對(duì)有效的計(jì)算過程，即算法，進(jìn)行形式化的描述忽略模型的

4、存儲(chǔ)容量在內(nèi)的一些枝節(jié)問題，只考慮算法的基本特征形式模型的特征 具有有窮描述過程必須是由離散的、可以機(jī)械執(zhí)行的步驟組成可計(jì)算性圖靈可計(jì)算性任一過程是能行的能夠具體表現(xiàn)在一個(gè)算法中，當(dāng)且僅當(dāng)它能夠被一臺(tái)圖靈機(jī)實(shí)現(xiàn)9.1 基本概念基本模型包括一個(gè)有窮控制器一條含有無窮多個(gè)帶方格的輸入帶一個(gè)讀頭 一個(gè)移動(dòng)將完成以下三個(gè)動(dòng)作改變有窮控制器的狀態(tài)在當(dāng)前所讀符號(hào)所在的帶方格中寫下一個(gè)符號(hào)將讀頭向右或者向左移一格讀頭輸入帶9.1.1 基本圖靈機(jī)圖靈機(jī)(Turing machine)/基本的圖靈機(jī)TM M=(Q, , , , q0 , B , F) ，Q：狀態(tài)的有窮集合，qQ，q為M的一個(gè)狀態(tài)q0Q：M的開始

5、狀態(tài)，對(duì)于一個(gè)給定的輸入串，M從狀態(tài)q0啟動(dòng)，讀頭正注視著輸入帶最左端的符號(hào)FQ：M的終止?fàn)顟B(tài)集，qF，q為M的一個(gè)終止?fàn)顟B(tài)與FA和PDA不同，一般地，一旦M進(jìn)入終止?fàn)顟B(tài)，它就停止運(yùn)行 為帶符號(hào)表(tape symbol)，X，X為M的一個(gè)帶符號(hào)，表示在M的運(yùn)行過程中，X可以在某一時(shí)刻出現(xiàn)在輸入帶上B：空白符(blank symbol)，含有空白符的帶方格被認(rèn)為是空的-B：輸入字母表，a，a為M的一個(gè)輸入符號(hào)；除了空白符號(hào)B之外，只有中的符號(hào)才能在M啟動(dòng)時(shí)出現(xiàn)在輸入帶上 圖靈機(jī)(Turing machine)/基本的圖靈機(jī)（續(xù)）TM M=(Q, , , , q0 , B , F) ，：QQR,

6、 L，為M的移動(dòng)函數(shù)(transaction function)。 (q , X)=(p , Y, R)：M在狀態(tài)q讀入符號(hào)X，將狀態(tài)改為p，并在這個(gè)X所在的帶方格中寫下符號(hào)Y，然后將讀頭向右移一格；(q , X)=(p , Y , L)表示M在狀態(tài)q讀入符號(hào)X，將狀態(tài)改為p，并在這個(gè)X所在的帶方格中寫下符號(hào)Y，然后將讀頭向左移一格。 q Xp Y X X Xq Xp X X Y X X X9.1.1 基本圖靈機(jī)例 9-1 設(shè)M1=(q0, q1, q2, 0, 1, 0, 1, B, , q0 , B ,q2)，其中的定義如下，(q0, 0)= (q0, 0, R)(q0, 1)= (q1,

7、 1, R)(q1, 0)= (q1, 0, R)(q1, B)= (q2, B, R) 對(duì)于此定義，也可以用下表表示01Bq0(q0, 0, R)(q1, 1, R)q1(q1, 0, R)(q2, B, R)q2在狀態(tài)q0,一旦遇上符號(hào)1，進(jìn)入狀態(tài)q1，遇上符號(hào)B，則進(jìn)入終止?fàn)顟B(tài)含且只含一個(gè)1的0，1串才能將M1引導(dǎo)到終止?fàn)顟B(tài)9.1.1 基本圖靈機(jī)定義9.2 及時(shí)描述 (instantaneous description, ID) 設(shè)TM M=(Q, , , , q0 , B , F) ， 12*，qQ， 1q2稱為M的及時(shí)描述，其中q為M的當(dāng)前狀態(tài)。1 2： 當(dāng)M的讀頭注視的符號(hào)右邊還有

8、非空白符時(shí)，12為M的輸入帶最左端到最右的非空白符號(hào)組成的符號(hào)串； 否則， 12是M的輸入帶最左端到M的讀頭注視的帶方格中的符號(hào)組成的符號(hào)串M正注視著2的最左符號(hào)。 Yq X X Y X Y B1=XXX2=YYYq X X X Y B1=XXX2=Y設(shè)X1X2Xi-1qXiXi+1Xn是M的一個(gè)ID (1) 如果(q, Xi)=(p, Y, R)，則，M的下一個(gè)ID為X1X2Xi-1YpXi+1Xn 記作 X1X2Xi-1qXiXi+1XnM X1X2Xi-1YpXi+1Xn 表示M在ID X1X2Xi-1qXiXi+1Xn下，經(jīng)過一次移動(dòng)，將ID變成X1X2Xi-1YpXi+1Xn 。 X

9、6q X2 X3 X5 X1 X4 B X6p X2 X3 X5 X1 Y B(2) 如果(q, Xi)=(p, Y, L)則，當(dāng)i1時(shí)，M的下一個(gè)ID為 X1X2Xi-2pXi-1YXi+1Xn記作 X1X2Xi-1qXiXi+1XnM X1X2pXi-1YXi+1Xn,表示M在ID X1X2Xi-1qXiXi+1Xn下，經(jīng)過一次移動(dòng)，將ID變成X1X2pXi-1YXi+1Xn； X6q X2 X3 X5 X1 X4 B X6p X2 X3 X5 X1 Y B設(shè)X1X2Xi-1qXiXi+1Xn是M的一個(gè)ID 設(shè)X1X2Xi-1qXiXi+1Xn是M的一個(gè)ID M是*Q*Q*上的一個(gè)二元關(guān)系

10、 Mn表示M的n次冪：Mn =(M)nM+表示M的正閉包：M+ =(M)+M*表示M的克林閉包：M* =(M)*在意義明確時(shí)，分別用、n 、+、*表示M 、Mn、M+、M*。例 9-2 例 9-1所給的M1在處理輸入串的過程中經(jīng)歷的ID變換序列。 （1）處理輸入串000100的過程中經(jīng)歷的ID的變換序列如下：q0000100M 0q000100M 00q00100M 000q0100 M 0001q100M 00010q10M 000100 q1M 000100Bq2 （2）處理輸入串0001的過程中經(jīng)歷的ID變換序列如下：q00001M 0q0001M 00q001M 000q01M 000

11、1q1M 0001Bq2（3）處理輸入串000101的過程中經(jīng)歷的ID變換序列如下：q0000101M 0q000101M 00q00101M 000q0101M 0001q101M 00010q11（4）處理輸入串1的過程中經(jīng)歷的ID變換序列如下：q01M 1q1M 1Bq2（5）處理輸入串00000的過程中經(jīng)歷的ID變換序列如下：q000000M 0q00000M 00q0000M 000q000M 0000 q00M 00000q0B(q0, 0)= (q0, 0, R)(q0, 1)= (q1, 1, R)(q1, 0)= (q1, 0, R)(q1, B)= (q2, B, R) 符

12、號(hào)B不是輸入符號(hào)，輸入串不含B，但在輸入串后的就是B不被M1接受9.1.1 基本圖靈機(jī)定義9.3 設(shè)TM M=(Q, , , , q0 , B , F)， M接受的語(yǔ)言 L(M)=x | x* , q0 xM* 1 q2 , qF , 1、2* 定義9.4 TM接受的語(yǔ)言叫做遞歸可枚舉語(yǔ)言(recursively enumerable language，r.e.)。如果存在TM M=(Q, , , , q0 , B , F)，L=L(M)，并且對(duì)每一個(gè)輸入串x，M都停機(jī)，則稱L為遞歸語(yǔ)言(recursively language)。 遞歸語(yǔ)言是遞歸可枚舉語(yǔ)言的子類例 9-3 設(shè)有M2=(q0,

13、 q1, q2, q3,0, 1,0, 1, B,q0 , B ,q3)，其中的定義如下所示，試分析M2接受的語(yǔ)言 (q0, 0)= (q0, 0, R) (q0, 1)= (q1, 1, R) (q1, 0)= (q1, 0, R) (q1, 1)= (q2, 1, R) (q2, 0)= (q2, 0, R) (q2, 1)= (q3, 1, R)9.1.1 基本圖靈機(jī)01Bq0(q0, 0, R)(q1, 1, R)q1(q1, 0, R)(q2, 1, R)q2(q2, 0, R)(q3, 1, R)q3 首先分析M2的工作過程。（1）處理輸入串00010101的過程中經(jīng)歷的ID變換序

14、列如下： q000010101 0q00010101 00q0010101 000q010101 0001q10101 00010q1101 000101 q201000101 0 q21 00010101q3M2在q0狀態(tài)下，遇到0時(shí)狀態(tài)仍然保持為q0，同時(shí)將讀頭向右移動(dòng)一格而指向下一個(gè)符號(hào)；過程：在q0狀態(tài)下遇到第一個(gè)1時(shí)狀態(tài)改為q1，并繼續(xù)右移讀頭，以尋找下一個(gè)1；在遇到第二個(gè)1時(shí)，動(dòng)作類似，只是將狀態(tài)改為q2；當(dāng)遇到第三個(gè)1時(shí)，進(jìn)入終止?fàn)顟B(tài)q3，此時(shí)它正好掃描完整個(gè)輸入符號(hào)串，表示符號(hào)串被M2接受。 01Bq0(q0, 0, R)(q1, 1, R)q1(q1, 0, R)(q2, 1

15、, R)q2(q2, 0, R)(q3, 1, R)q3（2）處理輸入串1001100101100的過程中經(jīng)歷的ID變換序列如下： q01001100101100 1q1001100101100 10 q101100101100 100q11100101100 1001 q210010110010011q300101100過程：M2遇到第三個(gè)1時(shí)，進(jìn)入終止?fàn)顟B(tài)q3，輸入串的后綴00101100還沒有被處理。由于M2已經(jīng)進(jìn)入終止?fàn)顟B(tài)，表示符號(hào)串1001100101100被M2接受 01Bq0(q0, 0, R)(q1, 1, R)q1(q1, 0, R)(q2, 1, R)q2(q2, 0, R

16、)(q3, 1, R)q3（3）處理輸入串000101000的過程中經(jīng)歷的ID變換序列如下： q0000101000 0q000101000 00q00101000 000q0101000 0001q101000 00010q11000 000101q2000 0001010 q200 00010100 q20 000101000 q2B過程：當(dāng)M2的ID變?yōu)?00101000q2B時(shí)，因?yàn)闊o法進(jìn)行下一個(gè)移動(dòng)而停機(jī),不接受輸入串00010100001Bq0(q0, 0, R)(q1, 1, R)q1(q1, 0, R)(q2, 1, R)q2(q2, 0, R)(q3, 1, R)q3M2接受

17、的語(yǔ)言是字母表0，1上那些至少含有3個(gè)1的0、1符號(hào)串如何構(gòu)造出接受字母表0，1上那些含且恰含有3個(gè)1的符號(hào)串的TM?9.1.1 基本圖靈機(jī)例 9-4 構(gòu)造TM M3，使L(M)=0n1n2n | n1。 分析：最為原始的方法來比較它們的個(gè)數(shù)是否是相同的：消除一個(gè)0、然后消除一個(gè)1，最后消除一個(gè)2。消除的0的帶方格上印刷一個(gè)X，在消除的1的帶方格上印刷一個(gè)Y，在消除的2的帶方格上印刷一個(gè)Z。正常情況下，輸入帶上的符號(hào)串的一般形式為 000011112222TM啟動(dòng)后，經(jīng)過一段運(yùn)行，輸入帶上的符號(hào)串的一般情況為 XX00YY11ZZ22BB需要給予邊界情況密切的關(guān)注。XXXXYYYYZZ22BB

18、XXXXYY11ZZ22BBXX00YYYYZZ22BBXX00YY11ZZZZBBXX00YYYYZZZZBB構(gòu)造思路在q0, 讀入0改寫為X, 讀頭向右移動(dòng)一位,到達(dá)狀態(tài)q1,R在q1, M3遇到第一個(gè)未標(biāo)記的1，將其標(biāo)記為Y, 讀頭向右移動(dòng)一位，然后進(jìn)入狀態(tài)q2在q2, M3遇到第一個(gè)未標(biāo)記的2時(shí)，將其標(biāo)記為Z然后進(jìn)入狀態(tài)q3，讀頭向左移動(dòng)一位在q3，M3將讀頭向左移到輸入帶中的最后一個(gè)X，并回到狀態(tài)q0，將讀頭指向第一個(gè)待處理的0,R,R,R,R,R, L, R, L, L, L, L,R,R,R,R移動(dòng)函數(shù)012XYZBq0(q1,X,R)(q4,Y,R)q1(q1,0,R)(q2,

19、Y,R)(q1,Y,R)q2(q2,1,R)(q3,Z,L)(q2,Z,R)q3(q3,0,L)(q3,1,L)(q0,X,R)(q3,Y,L)(q3,Z,L)q4(q4,Y,R)(q4,Z,R)(q5,B,R)q59.2 圖靈機(jī)作為非負(fù)整函數(shù)的計(jì)算模型 給非負(fù)整數(shù)進(jìn)行編碼 1進(jìn)制 用符號(hào)串0n表示非負(fù)整數(shù)n。用符號(hào)串 表示k元函數(shù) f(n1, n2, nk)的輸入，其中1用于將n1, n2, nk隔開如果f(n1, n2, nk)=m，則該TM的輸出為0m 。定義9-5 設(shè)有k元函數(shù)f(n1, n2, nk)=m，TM M=(Q, , , ,q0 , B , F)接受輸入串 ，輸出符號(hào)0m;

20、當(dāng)f(n1, n2, nk)無定義時(shí)，TM M沒有恰當(dāng)?shù)妮敵鼋o出。稱TM M計(jì)算k元函數(shù) f(n1, n2, nk)或 f(n1, n2, nk)為TM M計(jì)算的函數(shù)，也稱f是圖靈可計(jì)算的（Turing computable）。定義9-6 設(shè)有k元函數(shù)f(n1, n2, nk)=m，如果對(duì)于任意的n1, n2, nk ，f 均有定義，也就是計(jì)算 f的TM總能給出確定的輸出，則稱f為完全遞歸函數(shù);一般地，TM計(jì)算的函數(shù)稱為部分遞歸函數(shù)。例：整數(shù)的加、乘、冪等運(yùn)算都有確定的值，因次有限次使用這些去處構(gòu)造出來的函數(shù)都是可計(jì)算的；常用的算術(shù)去處函數(shù)都是完全遞歸函數(shù)。圖靈機(jī)構(gòu)造舉例例 9-5 構(gòu)造TM

21、M4，對(duì)于任意非負(fù)整數(shù)n，m，M4計(jì)算n+m。 分析：M4的輸入為0n10m，且M4停機(jī)時(shí)輸入帶上應(yīng)該出現(xiàn)形如0n+m的符號(hào)串。 下面針對(duì)n與m的不同取值進(jìn)行分析：當(dāng)n為0時(shí)，只用將1變成B就完成了計(jì)算，此時(shí)無需考察m是否為0；當(dāng)m為0時(shí)，需要掃描過表示n的符號(hào)0，并將1改為B；當(dāng)n和m都不為0時(shí)，我們需要將符號(hào)1改為0，并將最后一個(gè)0改為B。 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1當(dāng)n為0時(shí)，輸入串為10m在狀態(tài)q2向右掃描，直到遇到1，將其改為0，然后接著向右掃描，直到碰到B, 轉(zhuǎn)向狀態(tài)q3，讀頭向左把最后一個(gè)0改為B，使得一共只有m+n個(gè)0M4=(q0,

22、q1, q2, q3, 0,1, 0,1,B, , q0, B, q1)，其中 (q0，1)=(q1，B，R) (q0，0)=(q2，0，R) (q2，0)=(q2，0，R) (q2，1)=(q2，0，R) (q2，B)=(q3，B，L) (q3，0)=(q1，B，R),R,R,R,L,R,R例 9-6 構(gòu)造TM M5，對(duì)于任意非負(fù)整數(shù)n，m，M5計(jì)算如下函數(shù)： 基本思路輸入帶上為：0n10m逐個(gè)消除0m中0的過程中，對(duì)應(yīng)地逐個(gè)消除前0n中的0從左到右掃描，每消除前面的一個(gè)0，就到后面消除一個(gè)0特殊標(biāo)記符號(hào)X：消除前面的0，填入B；消除后面的0，填入X一次循環(huán)之后如果1前面找不到0，表示nm；

23、將帶上X符號(hào)都改成B，將1改成00010000B010000B01X000BB1X000BB1XX001前沒有0，此時(shí)nm每次1之前的0改為B后，讀頭向右掃描，直到找到1后第一個(gè)0，改為X.每次1之后的0改為X后，讀頭向左掃描，直到找到1前的最后一個(gè)0，改為B在狀態(tài)q0，遇到1之前，掃描到0，改為B，狀態(tài)到達(dá)q1，讀頭向右掃描在狀態(tài)q2, 在遇到0之前，讀頭向右掃描，狀態(tài)不變，直到到0，改為X，狀態(tài)到達(dá)q3在狀態(tài)q1，遇到1之前，掃描到0，讀頭向右掃描，狀態(tài)不變，直到遇到1，狀態(tài)到達(dá)q2在狀態(tài)q3，在遇到B之前，讀頭向左掃描，狀態(tài)不變，直到遇到B，此時(shí)讀頭向右，到達(dá)初始狀態(tài)q0, 一次循環(huán)結(jié)束

24、,R,R,R,R,R,L,L,R,R,R,R,L,R,L,L,LM5=(q0, q1, q2, q3, q4, q5, q6, 0,1, 0, 1, X, B, , q0, B, q6), 其中(q0, 0 )=(q1, B, R)(q0, 1 )=(q5, B, R)(q1, 0 )=(q1, 0, R)(q1, 1 )=(q1, 1, R)(q1, X )=(q2, X, R)(q2, X )=(q2, X, R)(q2, 0 )=(q3, X, L)(q2, B )=(q4, B, L)(q3, X )=(q3, X, L)(q3, 1 )=(q3, 1, L)(q3, 0 )=(q3,

25、 0, L)(q3, B )=(q0, B, R)(q4, X )=(q4, B, L)(q4, 1 )=(q6, 0, R)(q5, X )=(q5, B, R)(q5, 0 )=(q5, B, R)(q5, B )=(q6, B, R)。9.1.3 圖靈機(jī)的構(gòu)造 1. 狀態(tài)的有窮存儲(chǔ)功能的利用 例 9-7 構(gòu)造TM M6，使得L(M6)=x | x0,1*& x中至多含3個(gè)1。 分析：M6只用記錄已經(jīng)讀到的1的個(gè)數(shù)。q0表示當(dāng)前已經(jīng)讀到0個(gè)1；q1表示當(dāng)前已經(jīng)讀到1個(gè)1；q2表示當(dāng)前已經(jīng)讀到2個(gè)1；q3表示當(dāng)前已經(jīng)讀到3個(gè)1。進(jìn)入狀態(tài)q3后檢驗(yàn)在遇到B之前是否還有別的1,如果沒有則進(jìn)入終止

26、狀態(tài) q0q1q2q31. 狀態(tài)的有窮存儲(chǔ)功能M6=(q0, q1, q2, q3, qf, 0,1, 0,1,B, , q0, B, qf)(q0, 0 )=(q0, 0, R)(q0, 1 )=(q1, 1, R)(q0, B )=(qf, B, R)(q1, 0 )=(q1, 0, R)(q1, 1 )=(q2, 1, R)(q1, B )=(qf, B, R)(q2, 0 )=(q2, 0, R)(q2, 1 )=(q3, 1, R)(q2, B )=(qf, B, R)(q3, 0 )=(q3, 0, R)(q3, B )=(qf, B, R)(q3, 1 )=() 不定義問題：構(gòu)造

27、的TM接受恰含3個(gè)1的0，1串的圖靈機(jī)1. 狀態(tài)的有窮存儲(chǔ)功能TM是要接受且僅接受恰含3個(gè)1的0、1串的TM，對(duì)M6進(jìn)行修改，得到M7 L(M7) =x | x0,1*& x中含且僅含3個(gè)1 M7=(q0, q1, q2, q3, qf, 0, 1, 0, 1, B, , q0, B, qf) (q2, 0 )=(q2, 0, R)(q2, 1 )=(q3, 1, R)(q2, B )=(qf, B, R)(q3, 0 )=(q3, 0, R)(q3, B )=(qf, B, R)(q3, 1 )=() 不定義(q0, 0 )=(q0, 0, R)(q0, 1 )=(q1, 1, R)(q0,

28、 B )=(qf, B, R)(q1, 0 )=(q1, 0, R)(q1, 1 )=(q2, 1, R)(q1, B )=(qf, B, R)L(M8)=x | x0,1*& x中至少含3個(gè)1 M8=(q0, q1, q2, qf, 0, 1, 0, 1, B, , q0, B, qf)(q2, 0 )=(q2, 0, R)(q2, 1 )=(qf, 1, R)(q2, B )=(qf, B, R)(q3, 0 )=(q3, 0, R)(q3, B )=(qf, B, R)(q3, 1 )=() 不定義(q0, 0 )=(q0, 0, R)(q0, 1 )=(q1, 1, R)(q0, B

29、)=(qf, B, R)(q1, 0 )=(q1, 0, R)(q1, 1 )=(q2, 1, R)(q1, B )=(qf, B, R)1. 狀態(tài)的有窮存儲(chǔ)功能例9-8 構(gòu)造TM M9它的輸入字母表為0，1，現(xiàn)在要求M9在它的輸入符號(hào)串的尾部添加子串101。 分析：首先找到符號(hào)串的尾部；將給定符號(hào)串（如：101）中的符號(hào)依次地印刷在輸入帶上 方法：將待添加子串101存入有窮控制器q101 (qay, b)=(qay, b, R) (qay, B)=(qy, a, R)每印刷一個(gè)符號(hào)，就將它從有窮控制器的“存儲(chǔ)器”中刪去，當(dāng)該“存儲(chǔ)器”空時(shí)，TM就完成了工作。找到尾部B，把a(bǔ)寫入B所在的位置還

30、未找到尾部M9=(q101, q01, q1, q, 0, 1, 0, 1, B, , q101, B, q)其中的定義為：(q101, 0 )=(q101, 0, R)(q101, 1 )=(q101, 1, R)(q101, B )=(q01, 1, R)(q01, B )=(q1, 0, R)(q1, B )=(q, 1, R)未找到末尾找到末尾，依次把符號(hào)串101存到輸入帶1. 狀態(tài)的有窮存儲(chǔ)功能例 9-9 構(gòu)造TM M10它的輸入字母表為0，1，要求M10在它的輸入符號(hào)串的開始處添加子串101。 分析：將有窮控制器中的“存儲(chǔ)器”分成兩部分第一部分用來存放待添加的子串。第二部分用來存儲(chǔ)

31、因添加符號(hào)串當(dāng)前需要移動(dòng)的輸入帶上暫時(shí)無帶方格存放的子串。 狀態(tài)qx, yx待添加子串y當(dāng)前需要移動(dòng)的，輸入帶上暫時(shí)無帶方格存放的子串 把101加到222前面q101, 222 1q01,2 22 10q1,22 2 101q,222B 1012q,22B 10122q,2B 101222q, B 狀態(tài)qx, yx待添加子串y當(dāng)前需要移動(dòng)的，輸入帶上暫時(shí)無帶方格存放的子串 qx, 為開始狀態(tài)；q, 為終止?fàn)顟B(tài)。設(shè)a、b為輸入符號(hào)(qax, y, b) = (qx, yb, a, R)表示在沒有完成待插入子串的印刷之前，要將待插入子串的首字符印刷在TM當(dāng)前掃描的帶方格上。 (q, ay, b)

32、= (q, yb, a, R) 表示當(dāng)完成待插入子串的插入工作之后，必須將插入點(diǎn)之后的子串順序地向后移動(dòng)。 (q,ay, B) = (q, y, a, R) 表示讀頭當(dāng)前所指的帶方格為空白，現(xiàn)將“存儲(chǔ)器”的第二部分中的當(dāng)前首符號(hào)a印刷在此帶方格上，同時(shí)將這個(gè)符號(hào)從存儲(chǔ)器中刪除。一般形式為qx, yx待添加子串y當(dāng)前需要移動(dòng)的，輸入帶上暫時(shí)無帶方格存放的子串 例 9-9 構(gòu)造TM M10它的輸入字母表為0，1，要求M10在它的輸入符號(hào)串的開始處添加子串101。 2. 多道(multi-track)技術(shù) 例9-10 構(gòu)造M11，使L(M11)=xcy | x,y0,1+ 且 xy。 分析：以符號(hào)c

33、為分界線，逐個(gè)地將c前的符號(hào)與c后的符號(hào)進(jìn)行比較。什么時(shí)候進(jìn)入終止?fàn)顟B(tài)？當(dāng)發(fā)現(xiàn)對(duì)應(yīng)符號(hào)不同時(shí)當(dāng)發(fā)現(xiàn)x與y的長(zhǎng)度不相同發(fā)現(xiàn)它們相同而停機(jī)。例9-10 構(gòu)造M11，使L(M11)=xcy | x,y0,1+ 且 xy。方法：輸入帶分成兩個(gè)道：一個(gè)道存放被檢查的符號(hào)串，另一個(gè)存放標(biāo)記符當(dāng)對(duì)應(yīng)的符號(hào)被檢查過后，對(duì)應(yīng)的另一道上印刷一個(gè)標(biāo)記符，如當(dāng)對(duì)應(yīng)的符號(hào)還沒有被檢查時(shí)，則對(duì)應(yīng)的另一道上的符號(hào)是空白符B (B, b) (B, b) (B, d) (,a)(,a)（B,c) (B, b)已經(jīng)被檢查已經(jīng)被檢查思想很簡(jiǎn)單：找到x中第一個(gè)標(biāo)記為B的空格，標(biāo)記為讀頭向左找到c，并找到y(tǒng)中第一個(gè)標(biāo)記為B的空格，標(biāo)記

34、為判斷以上兩個(gè)空格的符號(hào)是否相等 若不相等，則進(jìn)入終止?fàn)顟B(tài)；否則重復(fù)以上過程，直到x,y中符號(hào)都標(biāo)記完，停機(jī)。xy (, b) (, b) (B, d) (,a)(,a)（B,c) (B, b)找到x中第一個(gè)標(biāo)記為B的空格，且符號(hào)不是c, 標(biāo)記為讀頭一直向右，直到找到c，表示x結(jié)束找到y(tǒng)中第一個(gè)標(biāo)記為B的空格，判斷兩個(gè)空格的符號(hào)是否相等相等讀頭向左，找到c讀頭繼續(xù)向左，直到找到x中第一個(gè)標(biāo)記為B的空格,L,R,L,L,R,R,R,R,R,R,R,L,R,RA, b, d, a1, a2, a3, a4, b1, b2, b3, b4都用來表示符號(hào) 0或1 M11=(q, q0, q1, p0,

35、 p1 , q, p, s, f, B,0, B,1, B,c, B,0, B,1, B,c, ,0, ,1, B,B, , q, B,B, f) (q, B,0 )=(q0, ,0, R) (q, B,1)=(q1, ,1, R)(qa, B,d)=(qa, B,d, R)(qa, B,c)=(pa, B,c, R)(pa, ,b)=(pa, ,b, R) (pa, B,a)=(p, ,a, L)(p, ,b)=(p, ,b, L) (p, B,c)=(q, B,c, L)(q, B,a)=(q, B,a, L)(q, ,a)=(q, ,a, R)(pa, B,b)=(f, B,b,R) (

36、pa, B,B)=(p, B,B, R)(s, ,b)=(s, ,b, R)(s, B,a)=(f, B,a, R)3. 子程序(subroutine)技術(shù) 將TM的設(shè)計(jì)看成是一種特殊的程序設(shè)計(jì)，將子程序的概念引進(jìn)來。一個(gè)完成某一個(gè)給定功能的TM M從一個(gè)狀態(tài)q開始，到達(dá)某一個(gè)固定的狀態(tài)f結(jié)束。將這兩個(gè)狀態(tài)作為另一個(gè)TM M的兩個(gè)一般的狀態(tài)。當(dāng)M進(jìn)入狀態(tài)q時(shí)，相當(dāng)于啟動(dòng)M(調(diào)用M對(duì)應(yīng)的子程序)；當(dāng)M進(jìn)入狀態(tài)f時(shí)，相當(dāng)于返回到M的狀態(tài)f。例9-11 構(gòu)造M12完成正整數(shù)的乘法運(yùn)算。 分析:設(shè)兩個(gè)正整數(shù)分別為n和m輸入串為0n10m 。輸出應(yīng)該為0n*m 。算法思想：每次將0n中的一個(gè)0改成B，就

37、在輸入串的后面復(fù)寫m個(gè)0。001000B01000000BB1000000000?001000B010001B010001q002103 + Bq1011031B01q2031+ B01q303103 B010001000q0q1Bq101031+B011q2031q2初始化：將第一個(gè)0變成B，并在最后一個(gè)0后寫上1從狀態(tài)q1開始，掃描過前n個(gè)0中剩余的0和第一個(gè)1，將讀頭指向后m個(gè)0的第一個(gè)，此時(shí)的狀態(tài)為q2調(diào)用子程序，在最后一個(gè)1后面復(fù)寫000，到達(dá)狀態(tài)q3B01q303103 + BBq1103103B BB10001000Bq3q1BB10001000000Bq4BBq1106B 當(dāng)復(fù)

38、寫完2*3=6個(gè)0后，清除輸入帶上除這6個(gè)0外的其他非空白符號(hào) ，進(jìn)入終止?fàn)顟B(tài)q4正整數(shù)的乘法運(yùn)算（1）初始化。完成將第一個(gè)0變成B，并在最后一個(gè)0后寫上1。我們用q0表示啟動(dòng)狀態(tài)，用q1表示完成初始化后的狀態(tài)。首先，消除前n個(gè)0中的第一個(gè)0，q00n10m + Bq10n-110m1（2）主控系統(tǒng)。從狀態(tài)q1開始，掃描過前n個(gè)0中剩余的0和第一個(gè)1，將讀頭指向m個(gè)0的第一個(gè)，此時(shí)的狀態(tài)為q2。其ID變化為Bhq10n-h10m10m*(h-1)B + Bh0n-h1 q20m10m*(h-1)B ，然后調(diào)用子程序當(dāng)子程序完成m個(gè)0的復(fù)寫后，回到q3。這個(gè)狀態(tài)相當(dāng)于子程序的返回（終止）狀態(tài)。然

39、后在q3狀態(tài)下，將讀頭移回到前n個(gè)0中剩余的0中的第一個(gè)0，并將這個(gè)0改成B，進(jìn)入q1狀態(tài)，準(zhǔn)備進(jìn)行下一次循環(huán) Bh0n-h1 q30m10m*hB + Bh+1q10n-h-110m10m*hB 當(dāng)完成m*n個(gè)0的復(fù)寫之后，清除輸入帶上除了這m*n個(gè)0以外的其他非空白符號(hào)。q4為終止?fàn)顟B(tài) Bnq110m10m*nB + Bn+1+m+1 q4 0m*nB（3）子程序。完成將m個(gè)0復(fù)寫到后面的任務(wù)。從q2啟動(dòng)，到q3結(jié)束，返回到主控程序。Bh+10n-h-11 q20m10m*hB + Bh+10n-h-11 q30m10m*h+1B 9.2 圖靈機(jī)的變形 從不同的方面對(duì)TM進(jìn)行擴(kuò)充。雙向無窮

40、帶TM。多帶TM。不確定的TM。多維TM等。它們與基本的TM等價(jià)。好處：使相應(yīng)的構(gòu)造變得更容易 9.2.1 雙向無窮帶圖靈機(jī) 雙向無窮帶 (Turing machine with two-way infinite tape，TM) TM M=(Q, , , ,q0 , B , F)Q, , , ,q0 , B , F的意義同定義9-1。的即時(shí)描述ID同定義-2。允許M的讀頭處在輸入串的最左端時(shí)，仍然可以向左移動(dòng)。 M的當(dāng)前ID X1X2Xi-1qXiXi+1Xn 如果(q, Xi)=(p, Y, R)當(dāng)i1并且YB時(shí)，M的下一個(gè)ID為X1X2Xi-1YpXi+1Xn記作X1X2Xi-1qXiX

41、i+1XnM X1X2Xi-1YpXi+1Xn表示M在ID X1X2Xi-1qXiXi+1Xn下，經(jīng)過一次移動(dòng)，將ID變成X1X2Xi-1YpXi+1Xn 。當(dāng)i=1并且Y=B時(shí)，M的下一個(gè)ID為 pX2Xn記作 qX1X2XnM pX2Xn和基本TM在讀頭右邊全部是B時(shí)，這些B不在ID中出現(xiàn)一樣，當(dāng)雙向無窮帶TM的讀頭左邊全部是B時(shí)，這些B也不在該TM的ID中出現(xiàn)。 如果(q, Xi)=(p, Y, L)當(dāng)i1時(shí)，M的下一個(gè)ID為X1X2pXi-1YXi+1Xn記作X1X2Xi-1qXiXi+1XnM X1X2pXi-1YXi+1Xn表示M在ID X1X2Xi-1qXiXi+1n下，經(jīng)過一次

42、移動(dòng)，將ID變成X1X2pXi-1YXi+1Xn 。 當(dāng)i=1時(shí)，M的下一個(gè)ID為pBYX2Xn記作 qX1X2XnM pBYX2Xn表示M在ID qX1X2Xn下，經(jīng)過一次移動(dòng)，將ID變成pBYX2Xn。9.4.1 雙向無窮帶圖靈機(jī)定理9-1 對(duì)于任意一個(gè)雙向無窮帶TM M，存在一個(gè)等價(jià)的基本TM M。 證明要點(diǎn)： 雙向無窮存儲(chǔ)的模擬：用一個(gè)具有2個(gè)道的基本TM來模擬：一個(gè)道存放M開始啟動(dòng)時(shí)讀頭所注視的帶方格(A0所在的方格)及其右邊的所有帶方格中存放的內(nèi)容；另一個(gè)道按照相反的順序存放M開始啟動(dòng)時(shí)讀頭所注視的帶方格左邊的所有帶方格中存放的內(nèi)容。BA-nA-1A0A1Ai AmBBA0A1Ai

43、BCA-1A-iB2. 雙向移動(dòng)的模擬：在第1道上，移動(dòng)的方向與原來的移動(dòng)方向一致，在第2道上，移動(dòng)的方向與原來的移動(dòng)方向相反。 定理9-1 對(duì)于任意一個(gè)雙向無窮帶TM M，存在一個(gè)等價(jià)的基本TM M。 證明要點(diǎn)（續(xù)）BA-nA-1A0A1Ai AmBB9.4.2 多帶圖靈機(jī)多帶TM(multi-tape turing machine) 允許TM有多個(gè)雙向無窮帶，每個(gè)帶上有一個(gè)相互獨(dú)立的讀頭。 k帶TM在一次移動(dòng)中完成如下三個(gè)動(dòng)作 改變當(dāng)前狀態(tài)； 各個(gè)讀頭在自己所注視的帶方格上印刷一個(gè)希望的符號(hào)。 各個(gè)讀頭向各自希望的方向移動(dòng)一個(gè)帶方格。9.4.2 多帶圖靈機(jī)定理 9-2 多帶TM與基本的TM等價(jià)。分析 ：基本TM機(jī)是多帶TM的特例，因此只需證明對(duì)于做生意一個(gè)多帶TM M, 都有一個(gè)與之等價(jià)的基本TM M因?yàn)閱螏蜗驘o窮帶的基本TM可以實(shí)現(xiàn)對(duì)單帶雙向圖靈機(jī)的模擬，因此假設(shè)k個(gè)帶都是單向無窮的證明要點(diǎn)： 對(duì)一個(gè)k帶TM，用一條具有2k道的雙向無窮帶TM M，實(shí)現(xiàn)對(duì)這個(gè)k帶TMM的模擬。對(duì)應(yīng)M的每一條帶，M用兩個(gè)道來實(shí)現(xiàn)模擬。一條道用來存放對(duì)應(yīng)的帶的內(nèi)容，另一條道專門用來標(biāo)記對(duì)應(yīng)帶上的讀頭所在的位置。 帶1的內(nèi)容A0A1A10An An+1AmB讀頭1的位置帶2的內(nèi)容