計算理論第4章_圖靈機

1、1第4章 圖靈機許桂靖 楊 瑩 2Overviewn圖靈機（Turing Machine，TM），是計算機的一種簡單的數(shù)學模型。n歷史上，馮諾曼計算機的產(chǎn)生就是由圖靈機誘發(fā)的。n丘奇圖靈論題：一切合理的計算模型都等同于圖靈機.3類型類型 文文 法法 結(jié)結(jié) 構(gòu)構(gòu) 產(chǎn)產(chǎn) 生生 式式 形形 式式 限限 制制 條條 件件 0 短語結(jié)構(gòu)文法短語結(jié)構(gòu)文法 +,* Phrase Structure 上下文有關文法上下文有關文法 1A212 |12|1A2| 1 Context Sensitive 1，2* （CSG ） A , + 上下文無關文法上下文無關文法 A A,*2 Context Free （CF

2、G） 正正 右線性文法右線性文法 AxB，Cy A,B,C 3 規(guī)規(guī) 文文 左線性文法左線性文法 ABx，Cy x,yT* 法法4Overview 0型語言型語言 圖靈機圖靈機 1型語言型語言(CSL) 線性界限自動機線性界限自動機 2型語言型語言(CFL) 下推自動機下推自動機 3型語言型語言(正規(guī)集正規(guī)集)有限自動機有限自動機 5Overviewn圖靈機所定義的語言類-遞歸可枚舉集合n圖靈機所計算的整數(shù)函數(shù)類-部分遞歸函數(shù)n以圖靈機為模型,研究問題的可計算性，即確定該問題是可計算的、部分可計算的，還是不可計算的。6Overview4.1 圖靈機模型 4.2 圖靈機的變化和組合 4.3 通用

3、圖靈機4.4圖靈機可計算性74.1 圖靈機模型 84.1 圖靈機模型圖靈機模型定義定義4-1 圖靈機M = ( K, , , , q0, B,F)，其中 K是有窮的狀態(tài)集合； 是所允許的帶符號集合； B ，是空白符； ，B ，是輸入字符集合； F K，是終止狀態(tài)集合。，是終止狀態(tài)集合。 q0K, 是初始狀態(tài)；是初始狀態(tài)； 94.1 圖靈機模型圖靈機模型：KKL,R,S是圖靈機的動作(狀態(tài)轉(zhuǎn)移)函數(shù)，這里L表示讀頭左移一格；R表示讀頭右移一格；S表示讀頭不動； (q,a)=(p,b,z) 表示狀態(tài)q下讀頭所讀符號為a時，狀態(tài)轉(zhuǎn)移為p,讀頭符號變?yōu)閎，同時讀頭變化為z.104.1 圖靈機模型圖靈機

4、模型定義定義4-2 設當前帶上字符串為x1x2 xn，當前狀態(tài)為q，讀頭正在讀xi ，圖靈機的瞬時描述ID 為x1x2 xi-1 q xi xn114.1 圖靈機模型圖靈機模型n定義定義4-3 設當前的瞬時描述ID1= x1x2 xi-1 q xi xn若有(q, x i) = (p, y, L)，則圖靈機瞬時描述變?yōu)镮D2 = x 1x 2 x i-2p x i-1 y x i+1 x n；若有 (q, x i) = (p, y, R)，則圖靈機瞬時描述變?yōu)镮D2 = x1x2 xi-1 y pxi+1 xn。124.1 圖靈機模型圖靈機模型n定義定義4-3瞬時描述ID1經(jīng)過一步變?yōu)樗矔r描述

5、ID2，稱ID1與ID2具有一步變化關系，表示為 ID1ID2 若ID1經(jīng)過n步變?yōu)镮D2(n0)，即有ID1ID ID2稱ID1與ID2具有多步變化關系，簡記為 ID1 *ID2134.1 圖靈機模型圖靈機模型n定義定義4-4 對于圖靈機M = ( K, , , , q0, B, F)，定義圖靈機接受的語言集 L(M) 為L(M)=w|w* u0 u v q qf(u0*u*v* qKqf F q0w*u0qB*uqfv)144.1 圖靈機模型圖靈機模型n【例【例4-1】設計一個圖靈機，使得】設計一個圖靈機，使得 L(M) = 0 n1 n | n1。設計思路設計思路: 在帶上每當將一個在帶

6、上每當將一個0變?yōu)樽優(yōu)閄，就把，就把一個一個1變?yōu)樽優(yōu)閅。當將所有的。當將所有的0變?yōu)樽優(yōu)閄時，恰將時，恰將所有的所有的1變?yōu)樽優(yōu)閅，這個串就是合法的，最后，這個串就是合法的，最后將將X、Y分別還原為分別還原為0、1。154.1 圖靈機模型圖靈機模型164.1 圖靈機模型圖靈機模型【例【例4-2】 設計一個圖靈機，使之接受設計一個圖靈機，使之接受 L(M) = wcw | w a,b* 設計思路：在設計思路：在c左側(cè)，從左至右逐一字符，用狀態(tài)記左側(cè)，從左至右逐一字符，用狀態(tài)記下它并標志該符號為已處理符號，移至下它并標志該符號為已處理符號，移至c右側(cè)對應右側(cè)對應位置后，判斷是否是相同符號。若相同

7、，再返回位置后，判斷是否是相同符號。若相同，再返回c左側(cè)循環(huán)，直至所有符號比較完畢。最后將標志左側(cè)循環(huán)，直至所有符號比較完畢。最后將標志符號修改回原符號。在設計時，特別注意用狀態(tài)符號修改回原符號。在設計時，特別注意用狀態(tài)存貯符號的方法，這是圖靈機設計的重要方法之存貯符號的方法，這是圖靈機設計的重要方法之一。一。174.1 圖靈機模型圖靈機模型184.1 圖靈機模型圖靈機模型【例【例4-3】設計一個圖靈機，計算自然數(shù)】設計一個圖靈機，計算自然數(shù)n的的以以2為底的對數(shù)。為底的對數(shù)。用一進制表示輸入和輸出值。用一進制表示輸入和輸出值。an表示輸入表示輸入n, bm表示輸出表示輸出m.設計思路：從左到

8、右掃描帶，把所碰到的設計思路：從左到右掃描帶，把所碰到的a劃劃掉一個，留一個，并將計數(shù)器加掉一個，留一個，并將計數(shù)器加1。重復此。重復此過程，直至過程，直至a不復存在。這里，用字符不復存在。這里，用字符c表表示劃掉的字符。示劃掉的字符。194.1圖圖靈靈機機模模型型204.1 圖靈機模型圖靈機模型【例【例4-4】設計一個圖靈機，計算二個自然數(shù)】設計一個圖靈機，計算二個自然數(shù)m、n的減法：的減法： 設計時，整數(shù)設計時，整數(shù)n用用0n表示。開始時，帶上符號為表示。開始時，帶上符號為 0m10n，結(jié)束時，帶上符號為，結(jié)束時，帶上符號為0。每當在。每當在1的左邊的左邊將一個將一個0改變?yōu)楦淖優(yōu)锽，就在

9、，就在1的右邊將一個的右邊將一個0改為改為1，若若1的右邊無的右邊無0時，再將左邊改為時，再將左邊改為B的的0恢復回來?；謴突貋怼?m-n 若若mnmnmn= 0 否則否則214.1 圖靈機模型圖靈機模型R224.1 圖靈機模型圖靈機模型【例【例4-5】 設計圖靈機實現(xiàn)數(shù)字從一進制表示到設計圖靈機實現(xiàn)數(shù)字從一進制表示到二進制表示的轉(zhuǎn)換。二進制表示的轉(zhuǎn)換。這個圖靈機的設計可以仿例這個圖靈機的設計可以仿例4-3 ，不同在于每次循，不同在于每次循環(huán)時，要保留除以環(huán)時，要保留除以2的余數(shù)作為當前二進制位的值。的余數(shù)作為當前二進制位的值。注意這里首先計算出的是二進制的低位值，所以注意這里首先計算出的是二

10、進制的低位值，所以要將結(jié)果不斷右移以插入新生成的位，生成的結(jié)要將結(jié)果不斷右移以插入新生成的位，生成的結(jié)果是低位在右端。初始時，整數(shù)果是低位在右端。初始時，整數(shù)n用用an表示，結(jié)束表示，結(jié)束時，帶上是時，帶上是0、1構(gòu)成的二進制數(shù)。構(gòu)成的二進制數(shù)。234.1 圖靈機模型圖靈機模型R244.2 圖靈機的變化和組合圖靈機的變化和組合n4.2.1 雙向無窮帶圖靈機n4.2.2 多帶圖靈機n4.2.3 非確定圖靈機n4.2.4 多頭圖靈機n4.2.5 多維圖靈機n4.2.6 離線圖靈機 n4.2.7 圖靈機的組合n4.2.8 枚舉器254.2.1雙向無窮帶圖靈機定理定理4-1 L被一個具有雙向無窮帶的圖

11、靈機識別，被一個具有雙向無窮帶的圖靈機識別，當且僅當它被一個單向無限帶的圖靈機識別。當且僅當它被一個單向無限帶的圖靈機識別。證明：單向無限證明：單向無限TM模擬雙向無限模擬雙向無限TM，采用多道技，采用多道技術(shù)。術(shù)。264.2.2 多帶圖靈機274.2.2 多帶圖靈機n【例【例4-6】設計一個二帶圖靈機，使得 T(M)= | 0,1*。n這個問題的關鍵是比較字符串前后兩個部分，為此，首先要對帶上字符串計數(shù)：每二元素計數(shù)加1，按計數(shù)值將字符串分為前后兩個部分，并將它們分別存放于不同帶上，然后進行比較。 284.2.2 多帶圖靈機294.2.2 多帶圖靈機【例【例4-7】 設計二帶圖靈機，實現(xiàn)二進

12、制到一進制的轉(zhuǎn)換。設這個圖靈機為M7，其第一帶用作輸入帶，第二帶用作輸出帶。設計思路是從左到右掃描輸入帶上的二進制字符，并使用公式r*2+b生成輸出帶上一進制數(shù)，其中r是當前輸出帶上的一進制數(shù)，b是當前輸入帶上掃描的字符，這里的r*2就是將原輸出帶上的一進制數(shù)r復制一遍。例如：1001的一進制數(shù)計算過程。304.2.2 多帶圖靈機314.2.2 多帶圖靈機定理定理4-2 如果一個語言L被一個多帶圖靈機接受，它就能被一個單帶圖靈機接受。 324.2.3 非確定圖靈機【例【例4-8】下面的圖靈機就是不確定圖靈機。無向圖G中，從a出發(fā)合法路徑判定的不確定型圖靈機。334.2.3 非確定圖靈機n非確定

13、圖靈機由一個有窮控制器、一條帶和一個讀頭組成。對于一個給定的狀態(tài)和被讀頭掃描的帶符號，機器的下一個動作將有有窮個選擇。n設一個非確定圖靈機 M1=( K, ,q0, B, F)，除轉(zhuǎn)移函數(shù)外，其它同一般圖靈機的定義。轉(zhuǎn)移函數(shù)仍是從K到KL,R,S上的映射，但它可能有多個映射的像,即存在qK, a,(q,a)= (p1, b1, c1)(q,a)= (p2, b2, c2) (q,a)= (pr, br, cr)344.2.3 非確定圖靈機定理定理4-3 如果語言L被一個非確定圖靈機M1接受，則L將被某個確定圖靈機M2接受。354.2.4 多頭圖靈機n一個k頭圖靈機有k個讀頭，一個控制器和一條帶

14、，讀頭由1到k編號，圖靈機的一個動作由當前狀態(tài)和被每個讀頭所掃描的符號。在一個動作中，每個讀頭獨立地左移、右移或不動。n定理定理4-4 如果L被某個k個讀頭的圖靈機接受，則它能被一個單頭圖靈機接受。364.2.5 多維圖靈機多維圖靈機具有通常的有限控制器，但帶卻多維圖靈機具有通常的有限控制器，但帶卻由由k維單元陣列組成。這里，在所有維單元陣列組成。這里，在所有2k個方個方向上（向上（k個軸，每軸正、負兩個方向），都個軸，每軸正、負兩個方向），都是無限的，根據(jù)狀態(tài)和掃視的符號，該裝是無限的，根據(jù)狀態(tài)和掃視的符號，該裝置改變狀態(tài)，打印一個新的符號，在置改變狀態(tài)，打印一個新的符號，在2k個個方向上移

15、動它的讀頭，開始時，輸入沿著方向上移動它的讀頭，開始時，輸入沿著一個軸排列，讀頭在輸入的左端。一個軸排列，讀頭在輸入的左端。374.2.6 離線圖靈機定理定理4-5 如果L被一個二維圖靈機M1接受，那么L將被一個一維圖靈機M2接受。384.2.7 圖靈機的組合394.2.7 圖靈機的組合【例【例4-9】 設計一個TM ，完成乘法運算mn。開始時帶上符號為：0m10n1，結(jié)束時帶上符號為0mn，用子程序調(diào)用的方式完成。設計思想是：每當抹去左邊一個，就在第二個后面拷貝n個。當?shù)谝粋€的左邊全變?yōu)锽時，帶上就為10n10mn，再抹去10n1，帶上就剩0mn，即為所求。設計Copy子程序 這個子程序完成

16、在第二個拷貝n個的操作。 第1次被調(diào)用開始ID：Bm-11q10n1結(jié)束ID：Bm-11q50n10n第i次被調(diào)用開始ID：Bim-i1q10n10(i-1)n結(jié)束ID：Bim-i1q50n10in在拷貝時，每當將一個變成，就在末尾寫個。當0n變?yōu)?n時，就已在右邊加了0n。再將2變?yōu)?n。 404.2.7 圖靈機的組合設計主 MM= q0,q6,q7,q8,q9,q10,q11,q12,q13,0,1,0,1,2,B,q0, B, q13)開始ID為q00m10n1，進入Copy入口ID為B0m-11q10n1，為此，(q0,0)=(q6,B,R)(q6,0)=(q6,0,R) (q6,1)

17、=(q1,1,R)從Copy結(jié)束時的ID，進入主TM的開始ID(B0m-11q50n10nBq00m-110n10n)(q5,0)=(q7,0,L)(q7,1)=(q8,1,L)(q8,0)=(q9,0,L)(q9,0)=(q9,0,L) (q9,B)=(q0,B,R)善后處理：Bm1q50n10mn414.2.8 枚舉器424.2.8 枚舉器定理定理4-6 一個語言是圖靈可識別的，當且僅當有枚舉器枚舉它。證明：首先證明如果有枚舉器E枚舉語言L，則存在圖靈機M識別L。構(gòu)造M如下：對于任意輸入串w，運行E。每當E輸出一個串時，與w比較，若相等，接受w，并停機。顯然，M接受在E輸出序列中出現(xiàn)過的那

18、些串?，F(xiàn)在證明若有圖靈機M識別語言L，則有枚舉器E枚舉L。設L=w1，w2，w3，構(gòu)造E如下：對i=1,2,3,執(zhí)行如下步驟（1）對w1，w2，w3，, wi中的每一串，讓M以其作為輸入運行i步。（2）若在這個計算中，M接受wj，則打印wj，M接受w，它最終將出現(xiàn)在E的枚舉打印中。事實上，它可能在E的列表在出現(xiàn)無限多次，因為每一次重復運行，M在每一個串上都從頭開始運行。434.3 通用圖靈機通用圖靈機() 緩沖域帶的最左面是標記符，的右邊是|K|+|+2個單元構(gòu)成的緩沖（|K|、|分別是狀態(tài)集和字母集的元素數(shù)目）。() 的描述字域緩沖區(qū)域右邊緊接的是的描述字dM，以為開始標志，以個結(jié)束。對于轉(zhuǎn)

19、移函數(shù)(q,a)=(q,a,d)，我們用五元組表示為(q, a, q, a, d)，將順序調(diào)整為(q, a, a, d, q)。 dM就是由這樣的五元組組成的序列。對于每個五元組中的狀態(tài)和字符，我們用其序號的一進表示，其間用分隔，五元組間用個分隔。例如：若有(q,)=(q,)，表示成上面定義的五元組是(q,，,，q)，再用其序號表示為(2,0,2,0,3)，在U2的帶上表示為011101011101011110() 的輸入描述域的描述字域的右邊存放的是輸入串的編碼：用字母的序號表示該字母，并用分隔。該域以為起始標志。如輸入為111，則該串表示為：110110110444.3 通用圖靈機通用圖靈

20、機UTM U2模擬具體步驟如下：模擬具體步驟如下：步步0 將讀頭置于描述字區(qū)域的開始符號上。此時緩沖區(qū)將讀頭置于描述字區(qū)域的開始符號上。此時緩沖區(qū)域是；域是；步步1U2復寫標記或后面的狀態(tài)到緩沖域的初始位置，復寫標記或后面的狀態(tài)到緩沖域的初始位置，然后在其后面加一個輔助符號，讀寫頭右移到符號；然后在其后面加一個輔助符號，讀寫頭右移到符號；步步2 U2復寫后面的初始帶模式到緩沖區(qū)部分，即在之復寫后面的初始帶模式到緩沖區(qū)部分，即在之后；后；步步3 U2將改為將改為0，現(xiàn)緩沖區(qū)中包含當前狀態(tài)和掃描的字，現(xiàn)緩沖區(qū)中包含當前狀態(tài)和掃描的字母；母；步步4對描述字域進行搜索，查看前兩項匹配的元組。若所對描述

21、字域進行搜索，查看前兩項匹配的元組。若所有的五元組都不匹配，則表明停機，有的五元組都不匹配，則表明停機，U2也停機。若找也停機。若找到一個匹配的五元組，標記、表示正在比較的狀態(tài)或到一個匹配的五元組，標記、表示正在比較的狀態(tài)或符號；符號；454.3 通用圖靈機通用圖靈機步步5(找到匹配的五元組找到匹配的五元組)刪去緩沖區(qū)的內(nèi)容，并把標記右刪去緩沖區(qū)的內(nèi)容，并把標記右移一個符號，使處于該五元組的新符號的前面；移一個符號，使處于該五元組的新符號的前面；步步6用新符號代替標記后面的符號用新符號代替標記后面的符號(可能需擴充或壓縮原可能需擴充或壓縮原輸入描述域輸入描述域)，U2將標記右移至五元組的方向分

22、量前；將標記右移至五元組的方向分量前；步步7 U2計數(shù)方向分量中的個數(shù)，然后按要求向左或向計數(shù)方向分量中的個數(shù)，然后按要求向左或向右移動標記。若向左離開了輸入串，則右移動標記。若向左離開了輸入串，則U2停機；若停機；若向右離開了輸入串，向右離開了輸入串，U2必須添加一個表示下一個方格必須添加一個表示下一個方格的新的的新的“”串。當前串。當前U2描述字域標記后面不是結(jié)束描述字域標記后面不是結(jié)束狀態(tài)，則轉(zhuǎn)至步狀態(tài)，則轉(zhuǎn)至步1；否則接受輸入串并停機。；否則接受輸入串并停機。464.3 通用圖靈機通用圖靈機474.3 通用圖靈機通用圖靈機n對于任何一個圖靈機對于任何一個圖靈機M，都有一個確定的描，都有

23、一個確定的描述字述字dM，如在例，如在例4-10中中dM=1010101101100101110111010111001101101101101n將它看作一個二進制數(shù)，實質(zhì)上，它是一將它看作一個二進制數(shù)，實質(zhì)上，它是一個整數(shù)，因此按這個整數(shù)，因此按這 種表示，任何一個圖靈種表示，任何一個圖靈機都和一個整數(shù)相對應，這個整數(shù)，稱為機都和一個整數(shù)相對應，這個整數(shù)，稱為圖靈機的標記。圖靈機的標記。 484.4圖靈可計算性圖靈可計算性n4.4.1 圖靈可計算性函數(shù) n4.4.2 圖靈機的枚舉定理n4.4.3 圖靈機的計算限界 494.4.1 圖靈可計算性函數(shù)圖靈可計算性函數(shù) n定義定義4-5 函數(shù)函數(shù)f

24、(x1, x2, ,xn)是部分圖是部分圖靈可計算的，若有一圖靈程序靈可計算的，若有一圖靈程序P，使得，使得P(x1, x2, ,xn) = f(x1, x2, ,xn)n其中其中P(x1, x2, ,xn)是是P對應的函數(shù)，對應的函數(shù)，“=”表示若有定義，則值相等；否則，均表示若有定義，則值相等；否則，均無定義。無定義。504.4.1 圖靈可計算性函數(shù)圖靈可計算性函數(shù)定義定義4-6 函數(shù)f(x1, x2, ,xn)是全函數(shù)，若它對一切x1, x2, ,xn都有定義。定義定義4-7 函數(shù)f(x1, x2, ,xn)是圖靈可計算函數(shù)，若它是部分圖靈可計算的而且是全函數(shù)。514.4.1 圖靈可計算

25、性函數(shù)圖靈可計算性函數(shù)524.4.1 圖靈可計算性函數(shù)圖靈可計算性函數(shù)定理定理4-7 設設g1, g2, gm是是n元圖靈可計元圖靈可計算函數(shù)，算函數(shù)，h是是m元圖靈可計算函數(shù)，則復合元圖靈可計算函數(shù)，則復合函數(shù)函數(shù)f=h (g1,g2,gm)也是圖靈可計算的。也是圖靈可計算的。534.4.2 圖靈機的枚舉定理圖靈機的枚舉定理1圖靈機的標記 2圖靈可計算的重要定理定義定義4-8 若z是一個圖靈機M的標記，并且M計算部分函數(shù)g(x1,x2,xn)，則定義函數(shù)(n) 為(n)(z,x1,x2,xn)= g(x1,x2,xn)544.4.2 圖靈機的枚舉定理圖靈機的枚舉定理定理定理4-8 枚舉定理枚舉定理 對于每個自然數(shù)z，部分函數(shù)(n)(z,x1,x2,xn)是(部分)圖靈可計算函數(shù)。證明它能枚舉所