第五章圖靈機(jī)2014

1、2021-11-161第第5章章 圖靈機(jī)圖靈機(jī) 圖靈機(jī)圖靈機(jī)(Turing machine)是由圖靈是由圖靈(Alan MathisomTuring)在在1936年提出的，它是年提出的，它是一個通用的計(jì)算模型。一個通用的計(jì)算模型。 通過研究通過研究TM，來研究遞歸可枚舉集，來研究遞歸可枚舉集(recursively enumerable set)和部分遞歸和部分遞歸函數(shù)函數(shù)(partial recursive function)。 對算法和可計(jì)算性進(jìn)行研究提供形式化描對算法和可計(jì)算性進(jìn)行研究提供形式化描述工具。述工具。2021-11-162圖靈機(jī)的基本模型圖靈機(jī)的基本模型圖靈機(jī)圖靈機(jī)(Turi

2、ng Machine ，簡記為，簡記為TM)的基本模型的基本模型是一個是一個確定的、單帶的自動機(jī)確定的、單帶的自動機(jī)。它有有限個狀態(tài)，有一條單向無窮延伸的存儲帶，它有有限個狀態(tài)，有一條單向無窮延伸的存儲帶，帶上劃分為無窮多個存儲單元。帶上劃分為無窮多個存儲單元。圖靈機(jī)通過圖靈機(jī)通過讀讀/寫寫頭，可從單元讀出符號，也可往頭，可從單元讀出符號，也可往單元上寫某些符號。單元上寫某些符號。圖靈機(jī)的讀圖靈機(jī)的讀/寫頭可在帶上寫頭可在帶上左、右移動左、右移動做讀做讀/寫工作。寫工作。2021-11-163定義定義 一個確定的、單帶圖靈機(jī)一個確定的、單帶圖靈機(jī)M是一個八元組：是一個八元組：M =（Q，B，

3、S ，F(xiàn)，R）其中：其中：o Q是有窮狀態(tài)集；是有窮狀態(tài)集；o 是有窮的輸入字母表；是有窮的輸入字母表；o 是有窮的帶字母表（是有窮的帶字母表（ ）；）；o : QQL,R，是轉(zhuǎn)移函數(shù)；，是轉(zhuǎn)移函數(shù)；o B-，是空白符號；，是空白符號；o SQ，是初始狀態(tài)；，是初始狀態(tài)；o FQ，是接受狀態(tài)；，是接受狀態(tài)；o RQ，是拒絕狀態(tài)。，是拒絕狀態(tài)。2021-11-164例例 給出語言給出語言L= 0n1n n1，構(gòu)造一個，構(gòu)造一個TM M，使，使L(M)=L。具體辦法是，具體辦法是， 當(dāng)當(dāng)TM的讀的讀/寫頭遇寫頭遇0時，將它改寫為時，將它改寫為X（或其它區(qū)別于（或其它區(qū)別于0的符號），然后到右邊去找

4、的符號），然后到右邊去找1； 找到找到1之后，將之后，將1改寫為改寫為Y（或其它區(qū)別于（或其它區(qū)別于1的符號）。的符號）。 這樣往返進(jìn)行下去，直到左邊的這樣往返進(jìn)行下去，直到左邊的0全部改為全部改為X，右邊，右邊的的1全部改為全部改為Y為止，如果沒有多余的為止，如果沒有多余的0或或1，TM就進(jìn)就進(jìn)入接受狀態(tài)表示接受。入接受狀態(tài)表示接受。 除此之外的其它各種情況，除此之外的其它各種情況，TM都不應(yīng)當(dāng)接受。都不應(yīng)當(dāng)接受。圖靈機(jī)的語言識別圖靈機(jī)的語言識別2021-11-1650 0 1 1 BX 0 1 1 B(q0,0)=(q1,X,R) 將將0改寫為改寫為X (q1,0)=(q1,0,R) 在在

5、q1的控制下向右找的控制下向右找1X 0 1 1 BX 0 Y 1 B(q1,1)=(q2,Y,L) 將將1改寫為改寫為Y,返回返回X 0 Y 1 B(q2,0)=(q2,0,L) 在在q2的控制下向左找的控制下向左找X后面的后面的0。X 0 Y 1 B (q2,X)=(q0,X,R) 遇遇X右移右移,狀態(tài)改為狀態(tài)改為q0 X X Y 1 B(q0,0)=(q1,X,R)X X Y 1 B(q1,Y)=(q1,Y,R) 向右找向右找1X X Y Y B(q1,1)=(q2,Y,L)X X Y Y B(q2,Y)=(q2,Y, L)(q0,Y)=(q3,Y, R) 0都改為都改為X，q0將遇到將

6、遇到Y(jié)，狀態(tài)改為，狀態(tài)改為q3 (q3 ，Y)=(q3 ，Y, R) 在在q3 的控制下，向右找的控制下，向右找B。 (q3 ,B)=(q4,B, 0) 0和和1的個數(shù)相等，進(jìn)入接受狀態(tài)。的個數(shù)相等，進(jìn)入接受狀態(tài)。(q2,X)=(q0,X,R) 2021-11-166(1)(3)(5)(q3 ,1)=(q5 ,1, 0) 1的個數(shù)多于的個數(shù)多于0的個數(shù)，到達(dá)拒絕狀態(tài)的個數(shù)，到達(dá)拒絕狀態(tài)q5 ，停機(jī)。，停機(jī)。 (11)(8)圖靈機(jī)圖靈機(jī)M1不接收不接收011的過程的過程 (1)(q0,0)=(q1,X,R) (2)(q1,0)=(q1,0,R) (3)(q1,1)=(q2,Y,L)(4)(q2,

7、0)=(q2,0,L) (5)(q2,X)=(q0,X,R)(6)(q1,Y)=(q1,Y,R)(7)(q2,Y)=(q2,Y, L)(8)(q0,Y)=(q3,Y, R)(9)(q3,Y)=(q3 ，Y, R) (10)(q3 ,B)=(q4,B, 0)0 1 1 Bq0X 1 1 Bq1X Y 1 Bq2X Y 1 Bq0X Y 1 Bq32021-11-167圖靈機(jī)圖靈機(jī)M1不接收不接收001的過程：的過程：(1)(2) (3)( 4 ) (5)(1) (6)(q1,B)=(q5,B,0) 0的個數(shù)多于的個數(shù)多于1的個數(shù)，拒絕。的個數(shù)，拒絕。 (12)(1)(q0,0)=(q1,X,R)

8、 (2)(q1,0)=(q1,0,R) (3)(q1,1)=(q2,Y,L)(4)(q2,0)=(q2,0,L) (5)(q2,X)=(q0,X,R)(6)(q1,Y)=(q1,Y,R)(7)(q2,Y)=(q2,Y, L)(8)(q0,Y)=(q3,Y, R)(9)(q3,Y)=(q3,Y, R) (10)(q3,B)=(q4,B, 0)(11)(q3 ,1)=(q5,1, 0)0 0 1 Bq0X 0 1 Bq1X 0 1 Bq1X 0 Y Bq2X 0 Y Bq2X 0 Y Bq0X X Y Bq1X X Y Bq12021-11-168圖靈機(jī)圖靈機(jī)M1不接收不接收010的過程：的過程：

9、(1) (3) (5)(q3,0)=(q5,0, 0) 1的后面還有的后面還有0，拒絕。，拒絕。 (13) (8)(1)(q0,0)=(q1,X,R) (3)(q1,1)=(q2,Y,L)(4)(q2,0)=(q2,0,L) (5)(q2,X)=(q0,X,R)(6)(q1,Y)=(q1,Y,R)(7)(q2,Y)=(q2,Y, L)(8)(q0,Y)=(q3,Y, R)(9)(q3,Y)=(q3,Y, R) (10)(q3,B)=(q4,B, 0)(11)(q3 ,1)=(q5,1, 0) (2)(q1,0)=(q1,0,R) (12)(q1,B)=(q5,B,0)0 1 0 Bq0X 1

10、0 Bq1X Y 0 Bq2X Y 0 Bq0X Y 0 Bq32021-11-1692021-11-1610狀態(tài)狀態(tài)符號符號01XYBq0 (q1,X, R) (q3 ,Y, R) q1(q1,0, R)(q2,Y, L) (q1 ,Y, R) (q5 ,B, 0) q2(q2 ,0, L) (q0 ,X, R) (q2,Y, L)q3(q5 ,0, 0) (q5 ,1, 0) (q3 ,Y, R) (q4 ,B, 0) 2021-11-1611q00011Xq1011 X0q111 Xq20Y1 q2X0Y1 Xq00Y1 XXq1Y1XXYq11 XXq2YY Xq2XYY XXq0YY

11、XXYq3YXXYYq3BXXYYBq4B 2021-11-1612例例 給出語言給出語言L= anbn+1cn+2 n0，構(gòu)造一個，構(gòu)造一個TM M接接受受L。 對于這類問題對于這類問題TM可以通過左右反復(fù)掃描、修改符號可以通過左右反復(fù)掃描、修改符號的辦法來實(shí)現(xiàn)對的辦法來實(shí)現(xiàn)對a，b，c的計(jì)數(shù)。具體方法是：的計(jì)數(shù)。具體方法是：M的的讀讀/寫頭經(jīng)過一次往返，將寫頭經(jīng)過一次往返，將a改寫為改寫為X，將，將b改寫為改寫為Y，將將c改寫為改寫為Z，經(jīng)過，經(jīng)過n次往返后，帶上符號就變?yōu)榇瓮岛?，帶上符號就變?yōu)閄XXYYYbZZZcc。然后，再處理多余的。然后，再處理多余的b和和c即可。即可。2021-

12、11-1613對于對于L= anbn+1cn+2 n0，構(gòu)造，構(gòu)造TM M：M =(q0 ,q1 ,q2 ,q3 ,q4 ,q5 ,q6 ,q7 ,q8 ，q9 ,a，b，c,X，Y，Z，凵凵a，b，c，凵，凵，q0 ，q8 ，q9 )， q0aabbbcccc (1)(q0 ,a)=(q1 ,X, R) Xq1abbbcccc 將將a改寫為改寫為X (2)(q1 ,a)=(q1 ,a, R) Xaq1bbbcccc 在在q1的控制下向右找的控制下向右找b (3)(q1 ,b)=(q2 ,Y, R) XaYq2bbcccc 將將b改寫為改寫為Y (4)(q2 ,b)=(q2 ,b, R) Xa

13、Ybbq2cccc 向右找向右找c (5)(q2 ,c)=(q3 ,Z, L) XaYbq3bZccc 將將c改寫為改寫為Z，返回。，返回。 (6)(q3 ,b)=(q3 ,b, L) Xaq3YbbZccc (7)(q3 ,Y)=(q3 ,Y, L) Xq3aYbbZccc (8)(q3 ,a)=(q3 ,a, L) q3XaYbbZccc (9)(q3 ,X)=(q0 ,X, R) Xq0aYbbZccc 遇遇X后改為后改為q0 ，轉(zhuǎn)（，轉(zhuǎn)（1） XXq1YbbZccc(1)(q0 ,a)=(q1 ,X, R) 2021-11-1614 XXYbbZccc (10)(q1 ,Y)=(q1

14、,Y, R) XXYq1bbZccc XXYYq2bZccc (3) (q1 ,b)=(q2 ,Y, R) XXYYbq2Zccc (4) (q2 ,b)=(q2 ,b, R) (11)(q2 ,Z)=(q2 ,Z, R) XXYYbZq2ccc XXYYbq3ZZcc (5) (q2 ,c)=(q3 ,Z, L) (12)(q3 ,Z)=(q3 ,Z, L) XXYYq3bZZcc XXYq3YbZZcc (6)(q3 ,b)=(q3 ,b, L) XXq3YYbZZcc (7)(q3 ,Y)=(q3 ,Y, L) Xq3XYYbZZcc (9)(q3 ,X)=(q0 ,X, R) (13)

15、(q0 ,Y)=(q4 ,Y, R) XXq0YYbZZcc 處理多余的處理多余的b，c (14)(q4 ,Y)=(q4 ,Y, R) XXYYq4bZZcc 處理多余的處理多余的b，c (15)(q4 ,b)=(q5 ,b, R) XXYYbq5ZZcc 遇到一個遇到一個b,正常情況正常情況,轉(zhuǎn)轉(zhuǎn)q5 。 (16)(q5 ,Z)=(q5 ,Z, R) XXYYbZZq5cc (17)(q5 ,c)=(q6 ,c, R) XXYYbZZcq6c (18)(q6 ,c)=(q7 ,c, R) XXYYbZZccq7 遇到兩個遇到兩個c后，轉(zhuǎn)后，轉(zhuǎn)q7 。 (19)(q7 ,B)=(q8 ,B,

16、R) q8 為接受狀態(tài)，接受。為接受狀態(tài)，接受。 (20)(q0 ,b)=(q5 ,b, R) 處理處理n=0的情況。的情況。2021-11-1615用矩陣形式表示以上的用矩陣形式表示以上的函數(shù)函數(shù)2021-11-1616圖靈機(jī)不但與其它自動機(jī)一樣有圖靈機(jī)不但與其它自動機(jī)一樣有“識別識別”的功能的功能 （當(dāng)它辨認(rèn)某串是（當(dāng)它辨認(rèn)某串是“合法合法” 就接受，否則就不接受），就接受，否則就不接受）， 而且有而且有“計(jì)算計(jì)算”的功能（在指定數(shù)表示法的情況下，的功能（在指定數(shù)表示法的情況下，實(shí)現(xiàn)整數(shù)函數(shù)的求值）。實(shí)現(xiàn)整數(shù)函數(shù)的求值）。為了簡單，用為了簡單，用“一進(jìn)制一進(jìn)制”表示整數(shù)：表示整數(shù)：n表示整

17、數(shù)表示整數(shù)n。 如果要計(jì)算整數(shù)函數(shù)如果要計(jì)算整數(shù)函數(shù)f(x,y),則可在則可在TM的帶上放的帶上放0 x10y( “1”是為了將是為了將x，y隔開，別的符號也可隔開，別的符號也可)， 然后通過然后通過TM的動作，將帶上符號改為的動作，將帶上符號改為0f（x，y）B，即表示出計(jì)算的結(jié)果。即表示出計(jì)算的結(jié)果。因?yàn)橛?jì)算因?yàn)橛?jì)算f(x,y)總是有結(jié)果的，沒有接受與不接受的總是有結(jié)果的，沒有接受與不接受的問題，但是還是用終結(jié)狀態(tài)表示計(jì)算結(jié)束比較好。問題，但是還是用終結(jié)狀態(tài)表示計(jì)算結(jié)束比較好。圖靈機(jī)的計(jì)算功能圖靈機(jī)的計(jì)算功能2021-11-1617例例 構(gòu)造一個構(gòu)造一個TM M，實(shí)現(xiàn)非負(fù)減法。設(shè)，實(shí)現(xiàn)非負(fù)

18、減法。設(shè)m，n1，m- n的定義為：的定義為： m-n = 設(shè)在開始時設(shè)在開始時M的帶上為的帶上為0m10nB，最終變?yōu)椋罱K變?yōu)锽n 0m-n B。思路是，思路是，1的左邊消去一個的左邊消去一個0，1的右邊也消去一個的右邊也消去一個0，表示一次減法，如此循環(huán)重復(fù)，直到右邊的表示一次減法，如此循環(huán)重復(fù)，直到右邊的0都消完為都消完為止；當(dāng)止；當(dāng)mn時，按定義做相應(yīng)處理。時，按定義做相應(yīng)處理。具體的消去方法，則可以多種多樣。這里采取的辦法是具體的消去方法，則可以多種多樣。這里采取的辦法是將左邊的將左邊的0變?yōu)樽優(yōu)锽，右邊的，右邊的0變?yōu)樽優(yōu)?（右邊的（右邊的0不能變?yōu)椴荒茏優(yōu)锽，以免和帶子后面的大

19、批空白符混淆），最后再處理那些以免和帶子后面的大批空白符混淆），最后再處理那些無用的無用的1。nm，0,nm,nm時當(dāng)時當(dāng)2021-11-1618M的構(gòu)造如下：的構(gòu)造如下： q00000100B(1)(q0，0)=(q1，B, R) Bq1000100B 將左邊的將左邊的0變?yōu)樽優(yōu)锽(2)(q1，0)=(q1，0, R) B000q1100B 在在q1的控制下向右找的控制下向右找1(3)(q1，1)=(q2，1, R) B0001q200B 找到后變?yōu)檎业胶笞優(yōu)閝2(4)(q2，0)=(q3，1, L) B000q3110B 將將1后面的第一個后面的第一個0變?yōu)樽優(yōu)?，返回，返回(5)(q3，

20、1)=(q3，1, L) B00q30110B 在在q3的控制下往左找空白的控制下往左找空白B(6)(q3，0)=(q3，0, L) q3B000110B 在在q3的控制下往左找空白的控制下往左找空白B(7)(q3，B)=(q0，B, R) Bq0000110B 轉(zhuǎn)轉(zhuǎn)(1)， BBq100110B (1) , BB00q1110B (2) , BB001q210B (8)(q2，1)=(q2，1, R) BB0011q20B BB001q311B （4） BB0q30111B (5) Bq3B00111B (6), BBq000111B （7） BBBq10111B (1) BBB0q1111

21、B (2) , BBB01q211B (3) BBB0111q2B (8)(9)(q2，B)=(q4，B, L) BBB011q41B q2遇到遇到B，表示，表示1的右面已沒有的右面已沒有0,表示運(yùn)算表示運(yùn)算q4已經(jīng)進(jìn)入尾聲，要消去所有的已經(jīng)進(jìn)入尾聲，要消去所有的1。(7)(q4，1)=(q4，B, L) BBBq40BBBB 在在q4的控制下，將的控制下，將1改寫為改寫為B。(8)(q4，0)=(q4，0, L) BBq4B0BBBB (9)(q4，B)=(q6，0, R) BB0q60BBBB 狀態(tài)狀態(tài)q6 表示減法結(jié)束表示減法結(jié)束2021-11-1619在在mn的情況，計(jì)算結(jié)果帶上符號為

22、的情況，計(jì)算結(jié)果帶上符號為Bn 0m-nB，0的個數(shù)已經(jīng)符合要的個數(shù)已經(jīng)符合要求。因?yàn)閳D靈機(jī)的任務(wù)是計(jì)算，只要輸入串按規(guī)定存放，總能得出結(jié)求。因?yàn)閳D靈機(jī)的任務(wù)是計(jì)算，只要輸入串按規(guī)定存放，總能得出結(jié)果，所以沒有接受或拒絕的問題。果，所以沒有接受或拒絕的問題。對于對于mn的情況，結(jié)果是的情況，結(jié)果是0，帶上應(yīng)當(dāng)全是空白符，因此需要單獨(dú)處，帶上應(yīng)當(dāng)全是空白符，因此需要單獨(dú)處理。理。 在上述反復(fù)消去在上述反復(fù)消去0的過程中，的過程中，1左邊的左邊的0先被消完先被消完: 0010000B BBq011100B當(dāng)當(dāng)q0與與1相遇時相遇時,相應(yīng)的相應(yīng)的函數(shù)為：函數(shù)為： (q0，1)=(q5,B, R) B

23、BBq51100B (q5，1)=(q5，B, R) BBBBBq500B (q5，0)=(q5，B, R) BBBBBBBq5B (q5，B)=(q6，B, R) BBBBBBBBq6 在在q5的控制下，將后面的的控制下，將后面的1和和0全部變?yōu)槿孔優(yōu)锽，直到遇見，直到遇見B才以狀態(tài)才以狀態(tài)q6結(jié)束。此時帶上全是空白符，表示結(jié)果為結(jié)束。此時帶上全是空白符，表示結(jié)果為0 。2021-11-1620 例例 構(gòu)造構(gòu)造TM M，對于任意非負(fù)整數(shù)，對于任意非負(fù)整數(shù)n，m，M計(jì)算計(jì)算m+n。 分析：分析：M 的輸入為的輸入為0n10m，輸出，輸出0n+m的符號串。的符號串。n和和m為為0的的情況需要特

24、殊考慮。情況需要特殊考慮。（1）當(dāng)）當(dāng)n和和m都不為都不為0時，我們需要將符號時，我們需要將符號1改為改為0，并將最，并將最后一個后一個0改為改為B。 q0000100B(q0，0)=(q1，0，R) 0q100100B(q1，0)=(q1，0，R) 000q1100B(q1，1)=(q1，0，R) 0000q100B 000000q1B(q1，B)=(q2，B，L) 00000q20B(q2，0)=(q3，B，R) 00000Bq3BM=(q0, q1, q2, q3, 0,1, 0,1,B, , q0, B, q3)2021-11-1621（2）當(dāng)）當(dāng)n為為0時，只用將時，只用將1變成變成

25、B就完成了計(jì)算，此時無需考就完成了計(jì)算，此時無需考察察m是否為是否為0； q0100B(q0，1)=(q3，B，R) Bq300B（3）當(dāng)）當(dāng)m為為0時，需要掃描過表示時，需要掃描過表示n的符號的符號0，并將，并將1改為改為B。 q00001B(q0，0)=(q1，0，R) 0q1001B(q1，0)=(q1，0，R) 000q11B(q1，1)=(q3，B，R) 000Bq3B2021-11-1622圖靈機(jī)的程序設(shè)計(jì)技術(shù)圖靈機(jī)的程序設(shè)計(jì)技術(shù)在狀態(tài)中存儲符號在狀態(tài)中存儲符號多道技術(shù)多道技術(shù)子程序技術(shù)子程序技術(shù)2021-11-1623在狀態(tài)中存儲符號在狀態(tài)中存儲符號例例 構(gòu)造一個構(gòu)造一個TM M

26、，它接受下述集合：，它接受下述集合：L=01，2* 10，2*20，1*。在字母表在字母表0，1，2上，上，L包含且僅包含滿足以下性質(zhì)的串：包含且僅包含滿足以下性質(zhì)的串：串中第一個符號可以是串中第一個符號可以是0，1或或2，但串中其余符號不可以和，但串中其余符號不可以和串的第一個符號相同。串的第一個符號相同。構(gòu)造構(gòu)造M的思想是：將第一個符號的思想是：將第一個符號“吸收吸收”到狀態(tài)上，構(gòu)成一到狀態(tài)上，構(gòu)成一個復(fù)合狀態(tài)（二元組）。個復(fù)合狀態(tài)（二元組）。然后這個復(fù)合狀態(tài)掃視其余符號，如果那些符號和復(fù)合狀態(tài)然后這個復(fù)合狀態(tài)掃視其余符號，如果那些符號和復(fù)合狀態(tài)所帶的符號均不相同，讀所帶的符號均不相同，讀

27、/寫頭就一直右移，直到遇空白符寫頭就一直右移，直到遇空白符而表示接受；而表示接受；否則就因輸入串不在否則就因輸入串不在L中而拒絕。中而拒絕。M =（q1，q2，q3，q1，0,q1，1,q1，2,0，1，2,0，1，2，B,B, q1，q2，q3），其中），其中函數(shù)為函數(shù)為:2021-11-1624 0121B(1) (q1，0)=(q1，0, 0, R) 0121B 將輸入串的第一個符號將輸入串的第一個符號“吸收吸收”到狀態(tài)上到狀態(tài)上(2) (q1，0,1)=(q1，0, 1, R) 0121B 遇非遇非0符號通過符號通過 (q1，0,2)=(q1，0, 2, R) 0121B 遇非遇非0符

28、號通過符號通過 0121B(3) (q1，0,B)=(q2 , B, 0) 0121B 遇空白符接受（遇空白符接受（q2為接受狀態(tài)）為接受狀態(tài)） 10220B 20110B (q1，1)=(q1，1, 1, R) (q1，1,0)=(q1，1, 0, R) 遇非遇非1符號通過符號通過 (q1，1,2)=(q1，1, 2, R) (q1，1,B)=(q2 , B, 0) (q1，2)=(q1，2, 2, R) (q1，2,0)=(q1，2, 0, R) 遇非遇非2符號通過符號通過 (q1，2,1)=(q1，2, 1, R) (q1，2,B)=(q2 , B, 0)其他其他函數(shù)都是拒絕的情況。函數(shù)

29、都是拒絕的情況。 例如，例如，(q1，0,0)表示以表示以0開頭的輸入串后面又遇到開頭的輸入串后面又遇到0，此串應(yīng)被拒絕，此串應(yīng)被拒絕,所以應(yīng)有所以應(yīng)有(q1，0,0)=（q3，0，0）（）（q3為拒絕狀態(tài)）。為拒絕狀態(tài)）。2021-11-1625用新狀態(tài)代替復(fù)合狀態(tài)用新狀態(tài)代替復(fù)合狀態(tài)從上可以看出，復(fù)合狀態(tài)實(shí)際上就是一種新的狀態(tài)，從上可以看出，復(fù)合狀態(tài)實(shí)際上就是一種新的狀態(tài)，可將例中的不同復(fù)合狀態(tài)用不同的新狀態(tài)表示：可將例中的不同復(fù)合狀態(tài)用不同的新狀態(tài)表示：(q0，0)=(q1, 0, R) 輸入串的第一個符號為輸入串的第一個符號為0，變，變1狀態(tài)狀態(tài)(q1, 1)=(q1，1, R) 遇非

30、遇非0符號通過符號通過(q1，2)=(q1，2, R) 遇非遇非0符號通過符號通過(q1，B)=(q4 , B, 0) 遇空白符接受（遇空白符接受（q4為接受狀態(tài)）為接受狀態(tài)）(q0，1)=(q2, 1, R) 輸入串的第一個符號為輸入串的第一個符號為1，變，變2狀態(tài)狀態(tài)(q2，0)=( q2, 0, R) 遇非遇非1符號通過符號通過(q2, 2)=( q2 , 2, R) 遇非遇非1符號通過符號通過(q2, B)=(q4 , B, 0) 遇空白符接受遇空白符接受(q0，2)=(q3, 2, R) 輸入串的第一個符號為輸入串的第一個符號為2，變，變3狀態(tài)狀態(tài)(q3，0)=( q3, 0, R)

31、 遇非遇非2符號通過符號通過(q3，1)=( q3, 1, R) 遇非遇非2符號通過符號通過(q3，B)=(q4 , B, 0) 遇空白符接受遇空白符接受2021-11-1626例例 構(gòu)造一個構(gòu)造一個TM M,它將帶上的非空白符號右移它將帶上的非空白符號右移2個單元格。個單元格。即將即將a1a2anB變?yōu)樽優(yōu)锽Ba1a2anB（ai為非空白符號，為非空白符號，i=1，2，n）。）。構(gòu)造構(gòu)造M的基本思路是，在某個狀態(tài)下首先將前兩個符號的基本思路是，在某個狀態(tài)下首先將前兩個符號a1，a2吸收進(jìn)來，構(gòu)成一個三元組狀態(tài)，再將前兩個位置變?yōu)榭瘴者M(jìn)來，構(gòu)成一個三元組狀態(tài)，再將前兩個位置變?yōu)榭瞻住Ｈ缓笤谌?/p>

32、元組狀態(tài)的控制下，將白。然后在三元組狀態(tài)的控制下，將a1放在放在a3的位置，將的位置，將a3吸收進(jìn)三元組代替吸收進(jìn)三元組代替a1，依此類推。直到最后遇空白符時，再，依此類推。直到最后遇空白符時，再將三元組中攜帶的最后兩個符號將三元組中攜帶的最后兩個符號an-1和和an放入最后兩個空格放入最后兩個空格內(nèi)，就完成了移動任務(wù)。內(nèi)，就完成了移動任務(wù)。2021-11-1627M的的函數(shù)如下：函數(shù)如下： abcdeBB(1) (q1, a)=( q1,B,a,B, R) BbcdeBB 將第一個符號吸到狀態(tài)上將第一個符號吸到狀態(tài)上(2) (q1,B,a, b)=( q1, a, b,B, R) BBcde

33、BB 將第二個符號也吸到狀態(tài)上將第二個符號也吸到狀態(tài)上(3) (q1, a,b, c)=( q1, b , c, a , R) BBadeBB 將將a放在放在c的位置的位置, c放在狀態(tài)上放在狀態(tài)上(3) (q1, b,c, d)=( q1, c , d, b , R) BBabeBB 將將b放在放在d的位置的位置, d放在狀態(tài)上放在狀態(tài)上(4) (q1, c,d, e)=( q1, d , e, c , R) BBabcBB 將將c放在放在e的位置的位置, e放在狀態(tài)上放在狀態(tài)上(5) (q1 , d,e, B)=(q1, B ,e , d, R) BBabcdB 在空白處放倒數(shù)第二個符號在

34、空白處放倒數(shù)第二個符號d(6) (q1 , B ,e, B)=( q2 , e, R) BBabcde 在下個空白處放最后符號在下個空白處放最后符號e， 移動完成。移動完成。2021-11-1628多道技術(shù)多道技術(shù)為了能保存和處理更復(fù)雜的數(shù)據(jù)，可以把為了能保存和處理更復(fù)雜的數(shù)據(jù)，可以把TM的帶的帶水平地劃分為若干道，在各道上可以存放不同的符水平地劃分為若干道，在各道上可以存放不同的符號。這并沒有改變號。這并沒有改變TM的基本模型，只是將帶符號的基本模型，只是將帶符號看成向量的集合，其中每個符號為一個看成向量的集合，其中每個符號為一個k維向量（維向量（k元組），這里元組），這里k為在帶上劃分的道

35、數(shù)。為在帶上劃分的道數(shù)。 2021-11-1629例例 構(gòu)造一個構(gòu)造一個TM M，接受，接受L= wcw wa,b+ 。為了解決這個問題，使用具有兩道的帶，和將符號吸收到狀為了解決這個問題，使用具有兩道的帶，和將符號吸收到狀態(tài)上這兩項(xiàng)技術(shù)。對態(tài)上這兩項(xiàng)技術(shù)。對M的設(shè)計(jì)思想是：輸入串放在的設(shè)計(jì)思想是：輸入串放在M的上道，的上道，故故=d，B d = a，b，c。例如，開始時帶上為以下形。例如，開始時帶上為以下形式：式：M從初始狀態(tài)從初始狀態(tài)q0出發(fā)，見到輸入串的第一個符號出發(fā)，見到輸入串的第一個符號a，將它吸，將它吸收到狀態(tài)上構(gòu)成二元組收到狀態(tài)上構(gòu)成二元組q1，a，并將，并將a的下面（第二道）空

36、的下面（第二道）空白符換成打鉤符號白符換成打鉤符號“”，表示看過。，表示看過。然后復(fù)合狀態(tài)然后復(fù)合狀態(tài)q1，a帶著這個帶著這個a越過中間的越過中間的c查看對應(yīng)位置，查看對應(yīng)位置，若對應(yīng)位置也是若對應(yīng)位置也是a，則在它的下面也打個鉤，表示通過。，則在它的下面也打個鉤，表示通過。然后再到左邊看第二個符號，依此類推。然后再到左邊看第二個符號，依此類推。2021-11-1630待到所有的符號（待到所有的符號（c除外）下面都打上鉤，說明輸入串在除外）下面都打上鉤，說明輸入串在L中，中，從而接受。從而接受。M在工作過程中（前面的在工作過程中（前面的b已查完，正在找已查完，正在找c后面后面的的b）帶上的情況

37、如下圖所示：）帶上的情況如下圖所示：根據(jù)以上思路，根據(jù)以上思路，M的具體構(gòu)造為：的具體構(gòu)造為：Q=q0 ,q8 ,q9qi ，d i=1，2，3，7；d=a，b，B。=d，B d=a，b，c。=d，X d=a，b，c；X=，BB。q0為初始狀態(tài)，為初始狀態(tài)，q8為終結(jié)狀態(tài)為終結(jié)狀態(tài),q9為拒絕狀為拒絕狀態(tài)。態(tài)。2021-11-1631函數(shù)定義為：函數(shù)定義為：(1)(q0 ,a，B)=(q1，a, a, R) abbacabbaB BBBBBBBBB(2)(q0 ,b，B)=(q1，b, b, R)(3)(q1，a ,b, B)=(q1，a, b, B, R ) abbacabbaB BBBBB

38、BBBB(4)(q1，a ,a, B)=(q1，a, a, B, R ) abbacabbaB BBBBBBBBB(5)(q1，b ,a, B)=(q1，b, a, B, R )(6)(q1，b ,b, B)=(q1，b, b, B, R )2021-11-1632(7)(q1，a ,c，B)=(q2，a, c,B, R) 找到中心找到中心c，狀態(tài)改為，狀態(tài)改為q2，a abbacabbaB BBBBBBBBB(8)(q1，b ,c，B)=(q2，b, c,B, R)(9)(q2，a ,a，B)=(q3，B, a, L) 找到找到c右邊的對應(yīng)符號，打鉤表示查右邊的對應(yīng)符號，打鉤表示查完，狀態(tài)改

39、為完，狀態(tài)改為q3，B，向左查下一符號。，向左查下一符號。 abbacabbaB BBBBBBBB(9)(q2，b ,b，B)=(q3，B, b, L)2021-11-1633(10)(q3，B ,c，B)=(q4，B, c,B, L) 越過中心越過中心c后，狀態(tài)改為后，狀態(tài)改為q4，B。 abbacabbaB BBBBBBBB(11)(q4，B ,d，B)=(q5，B, d,B, L) 遇尚未標(biāo)記的符號，狀態(tài)改為遇尚未標(biāo)記的符號，狀態(tài)改為q5，B，繼續(xù)向左。，繼續(xù)向左。 abbacabbaB BBBBBBBB(12)(q5，B ,d，B)=(q5，B, d,B, L) 在在q5，B的控制下，

40、繼續(xù)向左。的控制下，繼續(xù)向左。 abbacabbaB BBBBBBBB(13)(q5，B ,d，)=(q0, d, R) 轉(zhuǎn)（轉(zhuǎn)（1），繼續(xù)檢查下一對符號。），繼續(xù)檢查下一對符號。 abbacabbaB BBBBBBBBd=a，b2021-11-1634 a bbacabbaB BBBBBBB(14)(q2，d ,e，)=(q2，d, e, R) 在中心在中心c后，繼續(xù)找右邊的對應(yīng)符后，繼續(xù)找右邊的對應(yīng)符號號d，B。 a bbacabbaB BBBBBBB a bbaca bbaB BBB BBB(15)(q3，B ,d，)=(q3，B, d, L) 由（由（4），在），在q3，B的控制下，的

41、控制下，繼續(xù)向左找下一個尚未查看的符號。繼續(xù)向左找下一個尚未查看的符號。 a bbaca bbaB BBBBBBe=a，b2021-11-1635 a bbac a bbaB BBBBBB a b b a c a b b a B (16)(q4，B ,d，)=(q6，B, d, R) c左邊的符號都檢查完。左邊的符號都檢查完。(17)(q6，B ,c，B)=(q7，B, c，B, R) 又改變一次狀態(tài)，又改變一次狀態(tài)，由由q7，B控制向右找空白。控制向右找空白。(18)(q7，B ,d，)=( q7，B, d, R)(19)(q7，B ,B)=（q8，B，0） 左、右匹配成功，到達(dá)終結(jié)狀態(tài)。左

42、、右匹配成功，到達(dá)終結(jié)狀態(tài)。在這個例子中，非法輸入情況比較多，這里沒有列出。在這個例子中，非法輸入情況比較多，這里沒有列出。2021-11-1636子程序技術(shù)子程序技術(shù)子程序技術(shù)是將圖靈機(jī)中重復(fù)使用的某一部分劃分出來，做子程序技術(shù)是將圖靈機(jī)中重復(fù)使用的某一部分劃分出來，做為一個為一個“子程序子程序”。它有一個指定的開始狀態(tài)（不是整個圖靈機(jī)的初始狀態(tài)），它有一個指定的開始狀態(tài)（不是整個圖靈機(jī)的初始狀態(tài)），一個指定的返回狀態(tài)。一個指定的返回狀態(tài)。當(dāng)當(dāng)“主程序主程序”到達(dá)到達(dá)“子程序子程序”的開始狀態(tài)時，就相當(dāng)于調(diào)用的開始狀態(tài)時，就相當(dāng)于調(diào)用這個子程序；當(dāng)子程序到達(dá)它的返回狀態(tài)時，就相當(dāng)于返回這個子

43、程序；當(dāng)子程序到達(dá)它的返回狀態(tài)時，就相當(dāng)于返回到主程序，主程序可以從這個狀態(tài)開始再做其它工作。到主程序，主程序可以從這個狀態(tài)開始再做其它工作。子程序中除開始狀態(tài)和返回狀態(tài)與主程序公用外，其它在運(yùn)子程序中除開始狀態(tài)和返回狀態(tài)與主程序公用外，其它在運(yùn)行中所使用的狀態(tài)都是私有的，這些狀態(tài)在主程序或其它子行中所使用的狀態(tài)都是私有的，這些狀態(tài)在主程序或其它子程序中都不能再用。程序中都不能再用。2021-11-1637例例 構(gòu)造一個構(gòu)造一個TM M，實(shí)現(xiàn)整數(shù)的乘法運(yùn)算。，實(shí)現(xiàn)整數(shù)的乘法運(yùn)算。用圖靈機(jī)實(shí)現(xiàn)整數(shù)乘法用圖靈機(jī)實(shí)現(xiàn)整數(shù)乘法m*n就是當(dāng)帶上放就是當(dāng)帶上放0m10n之后，經(jīng)過之后，經(jīng)過TM M的的一系

44、列操作，最后帶上符號變?yōu)橐幌盗胁僮?，最后帶上符號變?yōu)?m n 。TM M處理這個問題是用最笨的方法，其基本思想是：當(dāng)從處理這個問題是用最笨的方法，其基本思想是：當(dāng)從1的左邊的左邊消去一個消去一個0后，在帶的后邊復(fù)制后，在帶的后邊復(fù)制n個個0(應(yīng)與原來的應(yīng)與原來的0n分隔開分隔開)；當(dāng)；當(dāng)1左左邊的邊的m個個0全部消完之后，后面自然得到乘積全部消完之后，后面自然得到乘積0m n ，然后再消去帶上，然后再消去帶上多余的符號就行了。多余的符號就行了。這可以看出，復(fù)制這可以看出，復(fù)制n個個0的工作是重復(fù)性的，而且是相對獨(dú)立的，因的工作是重復(fù)性的，而且是相對獨(dú)立的，因此將這部分工作分離出來，編成子程序的

45、形式比較合適。此將這部分工作分離出來，編成子程序的形式比較合適。2021-11-1638復(fù)制子程序復(fù)制子程序 0001B 0001000B (1)(q1 ,0)=(q2 ,2 ,R) 2 將將0改寫為改寫為2,以做標(biāo)記。以做標(biāo)記。(2)(q2 ,0)=(q2 ,0 ,R) 00 向右邊找空白向右邊找空白B。(3)(q2 ,1)=(q2 ,1 ,R) 1(4)(q2 ,B)=(q3 ,0 ,L) 0 找到空白后放找到空白后放0，返回。，返回。(5)(q3 ,0)=(q3 ,0 ,L)(6)(q3 ,1)=(q3 ,1 ,L)(7)(q3 ,2)=(q1 ,2 ,R) 20010B 重復(fù)重復(fù)(1)

46、，復(fù)制下一個，復(fù)制下一個0。 220100B 2221000B (8)(q1 ,1)=(q4 ,1 ,L) 3個個0都已復(fù)制完。都已復(fù)制完。(9)(q4 ,2)=(q4 ,0 ,L) 0001000 將將2恢復(fù)為恢復(fù)為0。(10)(q4 ,1)=(q5 ,1 ,R) 子程序出口，讀子程序出口，讀/寫頭仍在入口時的位置。寫頭仍在入口時的位置。2021-11-1639主程序主程序首先應(yīng)為反復(fù)調(diào)用子程序做好準(zhǔn)備，先將帶上的符號由首先應(yīng)為反復(fù)調(diào)用子程序做好準(zhǔn)備，先將帶上的符號由0m10nB變?yōu)樽優(yōu)锽0m-110n1B ，并將讀，并將讀/寫頭移至寫頭移至n個個0的第一個的第一個0處，狀態(tài)處，狀態(tài)變?yōu)樽優(yōu)?/p>

47、q1 ，就可以調(diào)用子程序了。實(shí)現(xiàn)上述工作序要下面一組，就可以調(diào)用子程序了。實(shí)現(xiàn)上述工作序要下面一組函數(shù)：函數(shù)：(1) (q0 ,0)=(q6 ，B, R) 先消去第一個先消去第一個0，準(zhǔn)備復(fù)制一次，準(zhǔn)備復(fù)制一次n個個0。(2) (q6 ,0)=(q6 ，0, R) (3) (q6 ,1)=(q7 ，1, R)(4) (q7 ,0)=(q7 ，0, R)(5) (q7 ,B)=(q8 ，1, L) 在最后放個在最后放個1返回。返回。此時帶上為此時帶上為B0m-110n1B (6) (q8 ,0)=(q8 ，0, L)(7) (q8 ,1)=(q1 ，1, R) 讀讀/寫頭移至指定位置，調(diào)用子程序

48、寫頭移至指定位置，調(diào)用子程序(8) (q7 ,1)=(q8 ，1, L) 因?yàn)楹筮叺囊驗(yàn)楹筮叺?只放一次，以后只放一次，以后q7再遇再遇1時時直接變?yōu)橹苯幼優(yōu)閝8 2021-11-1640當(dāng)子程序返回主程序時，狀態(tài)為當(dāng)子程序返回主程序時，狀態(tài)為q5 ，主程序應(yīng)控制從左邊再，主程序應(yīng)控制從左邊再消去一個消去一個0，才能再進(jìn)入子程序，因此還需要下面的一組，才能再進(jìn)入子程序，因此還需要下面的一組函函數(shù)：數(shù)：(9) (q5 ,0)=(q9 ，0, L) 一直向左找尚未消去的第一個一直向左找尚未消去的第一個0。(10)(q9 ,1)=(q10 ，1, L)(11)(q10 ,0)=(q11 ，0, L)

49、 (12)(q11 ,0)=(q11 ，0, L) (13)(q11 ,B)=(q0，B, R) 尚有未消去的尚有未消去的0，大循環(huán)重新開始。，大循環(huán)重新開始。(14)(q10 ,B)=(q12 ，B, R) m個個0已消完，大循環(huán)結(jié)束已消完，大循環(huán)結(jié)束。2021-11-1641當(dāng)狀態(tài)為當(dāng)狀態(tài)為q12時，帶上符號為時，帶上符號為 Bm 10n 10m nB ，為了，為了得出結(jié)果，還需要消去得出結(jié)果，還需要消去10n1，這由以下幾步來實(shí)現(xiàn)：，這由以下幾步來實(shí)現(xiàn)：(15)(q12 ,1)=(q13 ，B, R) 消去第一個消去第一個1。(16)(q13 ,0)=(q13 ，B, R) 消去消去n個

50、個0。(17)(q13 ,1)=(t ，B, 0) 消去最后一個消去最后一個1，計(jì)算結(jié)束。，計(jì)算結(jié)束。到此為止，帶上呈到此為止，帶上呈 Bm+n+2 0m nB 形式，作為形式，作為m*n的的結(jié)果表示，已經(jīng)足夠了。若求美觀，可以設(shè)法將結(jié)結(jié)果表示，已經(jīng)足夠了。若求美觀，可以設(shè)法將結(jié)果左移，使其在帶上呈果左移，使其在帶上呈0m nB 形式。形式。2021-11-1642圖靈機(jī)的變型圖靈機(jī)的變型雙向無限帶圖靈機(jī)雙向無限帶圖靈機(jī)多帶圖靈機(jī)多帶圖靈機(jī)非確定的圖靈機(jī)非確定的圖靈機(jī)雙棧機(jī)雙棧機(jī)做為枚舉器的圖靈機(jī)做為枚舉器的圖靈機(jī)2021-11-1643雙向無限帶雙向無限帶圖靈機(jī)圖靈機(jī)對圖靈機(jī)基本模型的第一個擴(kuò)充是將帶的單向無限延伸對圖靈機(jī)基本模型的第一個擴(kuò)充是將帶的單向無限延伸擴(kuò)大到雙向無限延伸，即不論輸入串放在帶的什么位置，擴(kuò)大到雙向無限延伸，即不論輸入串放在帶的什么位置，圖靈機(jī)的讀圖靈機(jī)的讀/寫頭都可以隨意向左、右移動。其余的記號寫頭都可以隨意向左、右移動。其余的記號和功能都和單向無限帶的圖靈機(jī)相同。和功能都和單向無限帶的圖靈機(jī)相同。圖靈機(jī)的這一擴(kuò)充并沒有增加圖靈機(jī)的