第二講 圖靈機模型.ppt

1、1,第2講 圖靈機模型,圖靈機(Turing machine)是由圖靈（Alan Mathisom Turing）在1936年提出的，它是一 個通用的計算模型。 通過研究圖靈機，來研究遞歸可枚舉集（recursively enumerable set）和部分地 歸函數(shù)（partial recursive function） 。 對算法和可計算性進行研究提供形式化描述工具。,2,主要內(nèi)容、重難點,主要內(nèi)容 圖靈機作為一個計算模型，它的基本定義，即時描述，圖靈機接受的語言；圖靈機的構(gòu)造技術(shù)；圖靈機的變形；Church-Turing論題；通用圖靈機。可計算語言、不可判定性、P-NP問題)。 重點 圖

2、靈機的定義、圖靈機的構(gòu)造。 難點 圖靈機的構(gòu)造。,3,2.1 基本概念,圖靈提出圖靈機具有以下兩個性質(zhì) 具有有窮描述。 過程必須是由離散的、可以機械執(zhí)行的步驟組成。 基本模型包括 一個有窮控制器。 一條含有無窮多個帶方格的輸入帶。 一個讀頭。 一個移動將完成以下三個動作 改變有窮控制器的狀態(tài)； 在當(dāng)前所讀符號所在的帶方格中印刷一個符號； 將讀頭向右或者向左移一格。,4,直觀物理模型,5,2.1.1 基本圖靈機,圖靈機（Turing machine）/基本的圖靈機 M=(Q, , , ,q0 , B , F) ， Q為狀態(tài)的有窮集合，qQ，q為M的一個狀態(tài)； q0Q，是M的開始狀態(tài)，對于一個給定

3、的輸入串，M從狀態(tài)q0啟動，讀頭正注視著輸入帶最左端的符號；,6,2.1.1 基本圖靈機,FQ，是M的終止?fàn)顟B(tài)集，qF，q為M的一個終止?fàn)顟B(tài)。與FA和PDA不同，一般地，一旦M進入終止?fàn)顟B(tài)，它就停止運行； 為帶符號表（tape symbol），X，X為M的一個帶符號，表示在M的運行過程中，X可以在某一時刻出現(xiàn)在輸入帶上；,7,2.1.1 基本圖靈機,B，被稱為空白符（blank symbol），含有空白符的帶方格被認(rèn)為是空的； -B為輸入字母表，a，a為M的一個輸入符號。除了空白符號B之外，只有中的符號才能在M啟動時出現(xiàn)在輸入帶上；,8,2.1.1 基本圖靈機,：QQR, L，為M的移動函數(shù)（

4、transaction function）。 (q , X)=(p , Y, R)表示M在狀態(tài)q讀入符號X，將狀態(tài)改為p，并在這個X所在的帶方格中印刷符號Y，然后將讀頭向右移一格； (q , X)=(p , Y , L)表示M在狀態(tài)q讀入符號X，將狀態(tài)改為p，并在這個X所在的帶方格中印刷符號Y，然后將讀頭向左移一格。,9,例子2-1說明,例 2-1 設(shè)M1=(q0, q1, q2,0, 1,0, 1, B,q0 , B ,q2)，其中的定義如下，對于此定義，也可以用表2-1表示。 (q0, 0)= (q0, 0, R) (q0, 1)= (q1, 1, R) (q1, 0)= (q1, 0,

5、R) (q1, B)= (q2, B, R),10,例子2-1說明,11,2.1.1 基本圖靈機,即時描述(instantaneous description, ID) 12*，qQ，1q2稱為M的即時描述 q為M的當(dāng)前狀態(tài)。 12為M的輸入帶最左端到最右的非空白符號組成的符號串或者是M的輸入帶最左端到M的讀頭注視的帶方格中的符號組成的符號串 M正注視著2的最左符號。,12,2.1.1 基本圖靈機,設(shè)X1X2Xi-1qXiXi+1Xn是M的一個ID 如果(q, Xi)=(p, Y, R)，則，M的下一個ID為X1X2Xi-1YpXi+1Xn 記作 X1X2Xi-1qXiXi+1XnM X1X2

6、Xi-1YpXi+1Xn 表示M在ID X1X2Xi-1qXiXi+1Xn下，經(jīng)過一次移動，將ID變成X1X2Xi-1YpXi+1Xn 。,13,2.1.1 基本圖靈機,如果(q, Xi)=(p, Y, L)則， 當(dāng)i1時，M的下一個ID為 X1X2pXi-1YXi+1Xn 記作 X1X2Xi-1qXiXi+1XnM X1X2pXi-1YXi+1Xn 表示M在ID X1X2Xi-1qXiXi+1Xn下，經(jīng)過一次移動，將ID變成X1X2pXi-1YXi+1Xn；,14,2.1.1 基本圖靈機,M是*Q*Q*上的一個二元關(guān)系 Mn表示M的n次冪：Mn =(M)n M+表示M的正閉包：M+ =(M)

7、+ M*表示M的克林閉包：M* =(M)* 在意義明確時，分別用、n 、+、*表示M 、Mn、M+、M*。,15,2.1.1 基本圖靈機,例 2-2. 例 2-1所給的M1在處理輸入串的過程中經(jīng)歷的ID變換序列。 （1）處理輸入串000100的過程中經(jīng)歷的ID的變換序列如下： q0000100M 0q000100M 00q00100 M 000q0100M 0001q100M 00010q10 M 000100 q1M 000100Bq2,16,2.1.1 基本圖靈機,（2）處理輸入串0001的過程中經(jīng)歷的ID變換序列如下： q00001M 0q0001M 00q001 M 000q01M 0

8、001q1M 0001Bq2 （3）處理輸入串000101的過程中經(jīng)歷的ID變換序列如下： q0000101M 0q000101M 00q00101 M 000q0101M 0001q101M 00010q11,17,2.1.1 基本圖靈機,（4）處理輸入串1的過程中經(jīng)歷的ID變換序列如下： q01M 1q1M 1Bq2 （5）處理輸入串00000的過程中經(jīng)歷的ID變換序列如下： q000000M 0q00000M 00q0000 M 000q000M 0000 q00M 00000q0B,18,2.1.1 基本圖靈機,圖靈機接受的語言 L(M)=x | x* & q0 xM* 1 q2 &

9、qF &1、2* 圖靈機接受的語言叫做遞歸可枚舉語言(recursively enumerable language，r.e.)。 如果存在圖靈機 M=(Q, , , ,q0 , B , F)，L=L(M)，并且對每一個輸入串x，M都停機，則稱L為遞歸語言(recursively language)。,19,2.1.1 基本圖靈機,例 2-3 設(shè)有M2=(q0, q1, q2, q3,0, 1,0, 1, B,q0 , B ,q3)，其中的定義如下： (q0, 0)= (q0, 0, R) (q0, 1)= (q1, 1, R) (q1, 0)= (q1, 0, R) (q1, 1)= (q2

10、, 1, R) (q2, 0)= (q2, 0, R) (q2, 1)= (q3, 1, R),20,2.1.1 基本圖靈機,21,2.1.1 基本圖靈機,為了弄清楚M2接受的語言，需要分析它的工作過程。 （1）處理輸入串00010101的過程中經(jīng)歷的ID變換序列如下： q000010101 0q00010101 00q0010101 000q010101 0001q10101 00010q1101 000101 q201000101 0 q21 00010101q3,22,2.1.1 基本圖靈機,M2在q0狀態(tài)下，遇到0時狀態(tài)仍然保持為q0，同時將讀頭向右移動一格而指向下一個符號； 在q1狀

11、態(tài)下遇到第一個1時狀態(tài)改為q1，并繼續(xù)右移讀頭，以尋找下一個1；在遇到第二個1時，動作類似，只是將狀態(tài)改為q2；當(dāng)遇到第三個1時，進入終止?fàn)顟B(tài)q3，此時它正好掃描完整個輸入符號串，表示符號串被M2接受。,23,2.1.1 基本圖靈機,（2）處理輸入串1001100101100的過程中經(jīng)歷的ID變換序列如下： q01001100101100 1q1001100101100 10 q101100101100 100q11100101100 1001 q210010110010011q300101100 M2遇到第三個1時，進入終止?fàn)顟B(tài)q3，輸入串的后綴00101100還沒有被處理。但是，由于M2已

12、經(jīng)進入終止?fàn)顟B(tài)，表示符號串1001100101100被M2接受。,24,2.1.1 基本圖靈機,（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時，因為無法進行下一個移動而停機,不接受輸入串000101000。,25,2.1.1 基本圖靈機,M2接受的語言是字母表0，1上那些至少含有3個1的

13、0、1符號串。請讀者考慮，如何構(gòu)造出接受字母表0，1上那些含且恰含有3個1的符號串的TM。,26,2.1.1 基本圖靈機,例 2-4 構(gòu)造TM M3，使L(M)=0n1n2n | n1。 分析： 不能通過“數(shù)”0、1、或者2的個數(shù)來實現(xiàn)檢查。 最為原始的方法來比較它們的個數(shù)是否是相同的：消除一個0、然后消除一個1，最后消除一個2。 消除的0的帶方格上印刷一個X，在消除的1的帶方格上印刷一個Y，在消除的2的帶方格上印刷一個Z。,27,2.1.1 基本圖靈機,正常情況下，輸入帶上的符號串的一般形式為 000011112222 TM啟動后，經(jīng)過一段運行，輸入帶上的符號串的一般情況為 XX00YY11

14、ZZ22BB 需要給予邊界情況密切的關(guān)注。,28,2.1.1 基本圖靈機,邊界情況 XXXXYYYYZZ22BB XXXXYY11ZZ22BB XX00YYYYZZ22BB XX00YY11ZZZZBB XX00YYYYZZZZBB,29,構(gòu)造思路,30,移動函數(shù),31,2.1.2 圖靈機作為非負(fù)整函數(shù)的計算模型,非負(fù)整數(shù)進行編碼 1進制 用符號串0n表示非負(fù)整數(shù)n。 用符號串,表示k元函數(shù)f(n1, n2, nk)的輸入。如果f(n1, n2, nk)=m，則該圖靈機的輸出為0m 。,32,2.1.2 圖靈機作為非負(fù)整函數(shù)的計算模型,圖靈可計算的(Turing computable) 設(shè)有k

15、元函數(shù)f(n1, n2, nk)=m，TM M=(Q, , , ,q0 , B , F)接受輸入串,輸出符號串0m；當(dāng)f(n1, n2, nk)無定義時，TM M沒有恰當(dāng)?shù)妮敵鼋o出。稱TM M計算k元函數(shù)f(n1, n2, nk)，也稱f(n1, n2, nk)為TM M計算的函數(shù)。也稱f是圖靈可計算的。,33,2.1.2 圖靈機作為非負(fù)整函數(shù)的計算模型,完全遞歸函數(shù)(total recursive function) 設(shè)有k元函數(shù)f(n1, n2, nk)，如果對于任意的n1, n2, nk ，f均有定義，也就是計算f的圖靈機總能給出確定的輸出，則稱f為完全遞歸函數(shù)。 部分遞歸函數(shù)(part

16、ial recursive function) 圖靈機計算的函數(shù)稱為部分遞歸函數(shù)。,34,2.1.2 圖靈機作為非負(fù)整函數(shù)的計算模型,例 2-5 構(gòu)造TM M4，對于任意非負(fù)整數(shù)n，m，M4計算m+n。 分析：M4的輸入為0n10m，輸出0n+m的符號串。n和m為0的情況需要特殊考慮。 （1）當(dāng)n為0時，只用將1變成B就完成了計算，此時無需考察m是否為0； （2）當(dāng)m為0時，需要掃描過表示n的符號0，并將1改為B。 （3）當(dāng)n和m都不為0時，我們需要將符號1改為0，并將最后一個0改為B。,35,構(gòu)造思路,36,M4,M4=(q0, q1, q2, q3, 0,1, 0,1,B, , q0, B

17、, 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),37,2.1.2 圖靈機作為非負(fù)整函數(shù)的計算模型,例 2-6 構(gòu)造圖靈機 M5，對于任意非負(fù)整數(shù)n，m，M5計算如下函數(shù)：,38,構(gòu)造思路,39,M5,M5=(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)

18、(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, 0, L) (q3, B )=(q0, B, R),40,M5,(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)。,41,2.1.3 圖靈機的

19、構(gòu)造,1. 狀態(tài)的有窮存儲功能的利用,2. 多道(multi-track)技術(shù),3. 子程序(subroutine)技術(shù),42,1. 狀態(tài)的有窮存儲功能的利用,例 2-7 構(gòu)造圖靈機 M6，使得L(M6)=x | x0,1*& x中至多含3個1。 分析：M6只用記錄已經(jīng)讀到的1的個數(shù)。 q0表示當(dāng)前已經(jīng)讀到0個1； q1表示當(dāng)前已經(jīng)讀到1個1； q2表示當(dāng)前已經(jīng)讀到2個1； q3表示當(dāng)前已經(jīng)讀到3個1。,43,1. 狀態(tài)的有窮存儲功能的利用,M6=(q0, q1, q2, q3, qf, 0,1, 0,1,B, , q0, B, qf),(q0, 0 )=(q0, 0, R) (q0, 1 )

20、=(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),44,1. 狀態(tài)的有窮存儲功能的利用,圖靈機是要接受且僅接受恰含3個1的0、1串的圖靈機，對M6進行修改，得到M7 L(M7) =x | x0,1*& x中含且僅含3個1 M7=(q0, q1, q2, q3, qf

21、, 0, 1, 0, 1, B, , q0, B, qf),45,L(M7) =x | x0,1*且 x中僅含3個1,(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) (q3, 0 )=(q3, 0, R) (q3, B )=(qf, B, R),46,L(M8)=x | x0,1*& x中至少含3個1,M8=(q0, q1, q2, qf, 0, 1, 0, 1, B, , q0, B, qf) (q0

22、, 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 )=(qf, 1, R),47,1. 狀態(tài)的有窮存儲功能的利用,例2-8 構(gòu)造圖靈機 M9它的輸入字母表為0，1，現(xiàn)在要求M9在它的輸入符號串的尾部添加子串101。 分析： 將待添加子串101存入窮控制器。 首先找到符號串的尾部。 將給定符號串中的符號依次地印刷在輸入帶上 每印刷一個符號，就將它從有窮控制器的“存儲器”中刪去，當(dāng)該“存儲器”空時，圖靈機就完成了工作。,48,1. 狀態(tài)的有窮

23、存儲功能的利用,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),49,1. 狀態(tài)的有窮存儲功能的利用,例2-9 構(gòu)造圖靈機 M10它的輸入字母表為0，1，要求M10在它的輸入符號串的開始處添加子串101。 將有窮控制器中的“存儲器”分成兩部分 第一部分用來存放待添加的子串。 第二部分用來存儲因添加符號串當(dāng)前

24、需要移動的輸入帶上暫時無帶方格存放的子串。 一般形式為qx, y x待添加子串 y當(dāng)前需要移動的輸入帶上暫時無帶方格存放的子串。,50,1.狀態(tài)的有窮存儲功能的利用,qx, 為開始狀態(tài)； q, 為終止?fàn)顟B(tài)。 設(shè)a、b為輸入符號 (qax, y, b) = (qx, yb, a, R) 表示在沒有完成待插入子串的印刷之前，要將待插入子串的首字符印刷在TM當(dāng)前掃描的帶方格上。,51,1. 狀態(tài)的有窮存儲功能的利用,(q,a y, b) = (q, yb, a, R) 表示當(dāng)完成待插入子串的插入工作之后，必須將插入點之后的子串順序地向后移動。 (q,a y, B) = (q, y, a, R) 表示

25、讀頭當(dāng)前所指的帶方格為空白，現(xiàn)將“存儲器”的第二部分中的當(dāng)前首符號a印刷在此帶方格上，同時將這個符號從存儲器中刪除。,52,2. 多道(multi-track)技術(shù),例2-10 構(gòu)造M11，使L(M11)=xcy | x,y0,1+ 且 xy。 分析： 以符號c為分界線，逐個地將c前的符號與c后的符號進行比較。 當(dāng)發(fā)現(xiàn)對應(yīng)符號不同時，就進入終止?fàn)顟B(tài)。 當(dāng)發(fā)現(xiàn)x與y的長度不相同而進入終止?fàn)顟B(tài)。 發(fā)現(xiàn)它們相同而停機。 一個道存放被檢查的符號串，另一個存放標(biāo)記符。,53,構(gòu)造思路,54,2. 多道(multi-track)技術(shù),M11=(q, q0, q1, p0, p1 , q, p, s, f,

26、 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),55,2. 多道(multi-track)技術(shù),(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

27、)=(f, B,b,R) (pa, B,B)=(p, B,B, R) (s, ,b)=(s, ,b, R) (s, B,a)=(f, B,a, R),56,3. 子程序(subroutine)技術(shù),將圖靈機的設(shè)計看成是一種特殊的程序設(shè)計，將子程序的概念引進來。 一個完成某一個給定功能的圖靈機 M從一個狀態(tài)q開始，到達某一個固定的狀態(tài)f結(jié)束。 將這兩個狀態(tài)作為另一個圖靈機 M的兩個一般的狀態(tài)。 當(dāng)M進入狀態(tài)q時，相當(dāng)于啟動M(調(diào)用M對應(yīng)的子程序)；當(dāng)M進入狀態(tài)f時，相當(dāng)于返回到M的狀態(tài)f。,57,3. 子程序(subroutine)技術(shù),例2-11 構(gòu)造M12完成正整數(shù)的乘法運算。 分析: 設(shè)兩

28、個正整數(shù)分別為m和n。 輸入串為0n10m 。 輸出應(yīng)該為0n*m 。 算法思想：每次將n個0中的1個0改成B，就在輸入串的后面復(fù)寫m個0。 在M12的運行過程中，輸入帶的內(nèi)容為 Bh0n-h10m10m*hB,58,正整數(shù)的乘法運算,（1）初始化。完成將第一個0變成B，并在最后一個0后寫上1。我們用q0表示啟動狀態(tài)，用q1表示完成初始化后的狀態(tài)。首先，消除前n個0中的第一個0， q00n10m + Bq10n-110m1 （2）主控系統(tǒng)。從狀態(tài)q1開始，掃描過前n個0中剩余的0和第一個1，將讀頭指向m個0的第一個，此時的狀態(tài)為q2。其ID變化為 Bhq10n-h10m10m*(h-1)B +

29、 Bh0n-h1 q20m10m*(h-1)B,59,正整數(shù)的乘法運算,當(dāng)子程序完成m個0的復(fù)寫后，回到q3。這個狀態(tài)相當(dāng)于子程序的返回（終止）狀態(tài)。然后在q3狀態(tài)下，將讀頭移回到前n個0中剩余的0中的第一個0，并將這個0改成B，進入q1狀態(tài)，準(zhǔn)備進行下一次循環(huán) Bh0n-h1 q30m10m*hB + Bh+1q10n-h-110m10m*hB,60,正整數(shù)的乘法運算,當(dāng)完成m*n個0的復(fù)寫之后，清除輸入帶上除了這m*n個0以外的其他非空白符號。q4為終止?fàn)顟B(tài) Bnq110m10m*nB + Bn+1+m+1 q4 0m*nB （3）子程序。完成將m個0復(fù)寫到后面的任務(wù)。從q2啟動，到q3結(jié)

30、束，返回到主控程序。 Bh+10n-h-11 q20m10m*hB + Bh+10n-h-11 q30m10m*h+1B,61,2.2 圖靈機的變形,從不同的方面對圖靈機進行擴充。 雙向無窮帶圖靈機。 多帶圖靈機。 不確定的圖靈機。 多維圖靈機等。 它們與基本的圖靈機等價。,62,2.2.1 雙向無窮帶圖靈機,物理模型,63,2.2.1 雙向無窮帶圖靈機,雙向無窮帶 (Turing machine with two-way infinite tape) 圖靈機 M=(Q, , , ,q0 , B , F) Q, , , ,q0 , B , F的意義同定義9-1。 的即時描述ID同定義-2。 允

31、許M的讀頭處在輸入串的最左端時，仍然可以向左移動。,64,2.2.1 雙向無窮帶圖靈機,M的當(dāng)前ID X1X2Xi-1qXiXi+1Xn 如果(q, Xi)=(p, Y, R) 當(dāng)i1并且YB時，M的下一個ID為 X1X2Xi-1YpXi+1Xn 記作 X1X2Xi-1qXiXi+1XnM X1X2Xi-1YpXi+1Xn 表示M在ID X1X2Xi-1qXiXi+1Xn下，經(jīng)過一次移動，將ID變成X1X2Xi-1YpXi+1Xn 。,65,2.2.1 雙向無窮帶圖靈機,當(dāng)i=1并且Y=B時，M的下一個ID為 pX2Xn 記作 qX1X2XnM pX2Xn 這就是說，和基本圖靈機在讀頭右邊全部

32、是B時，這些B不在ID中出現(xiàn)一樣，當(dāng)雙向無窮帶圖靈機的讀頭左邊全部是B時，這些B也不在該圖靈機的ID中出現(xiàn)。,66,2.2.1 雙向無窮帶圖靈機,如果(q, Xi)=(p, Y, L) 當(dāng)i1時，M的下一個ID為 X1X2pXi-1YXi+1Xn 記作 X1X2Xi-1qXiXi+1XnM X1X2pXi-1YXi+1Xn 表示M在ID X1X2Xi-1qXiXi+1n下，經(jīng)過一次移動，將ID變成X1X2pXi-1YXi+1Xn 。,67,2.2.1 雙向無窮帶圖靈機,當(dāng)i=1時，M的下一個ID為 pBYX2Xn 記作 qX1X2XnM pBYX2Xn 表示M在ID qX1X2Xn下，經(jīng)過一次

33、移動，將ID變成pBYX2Xn。,68,2.2.1 雙向無窮帶圖靈機,定理2-1 對于任意一個雙向無窮帶圖靈機M，存在一個等價的基本圖靈機M。 證明要點： 雙向無窮存儲的模擬：用一個具有2個道的基本TM來模擬：一個道存放M開始啟動時讀頭所注視的帶方格及其右邊的所有帶方格中存放的內(nèi)容；另一個道按照相反的順序存放開始啟動時讀頭所注視的帶方格左邊的所有帶方格中存放的內(nèi)容。 雙向移動的模擬：在第1道上，移動的方向與原來的移動方向一致，在第2道上，移動的方向與原來的移動方向相反。,69,用單向無窮帶模擬雙向無窮帶,70,2.2.2 多帶圖靈機,多帶圖靈機(multi-tape turing machin

34、e) 允許圖靈機有多個雙向無窮帶，每個帶上有一個相互獨立的讀頭。 k帶圖靈機在一次移動中完成如下三個動作 改變當(dāng)前狀態(tài)； 各個讀頭在自己所注視的帶方格上印刷一個希望的符號。 各個讀頭向各自希望的方向移動一個帶方格。,71,2.2.2 多帶圖靈機,72,2.2.2 多帶圖靈機,定理 2-2 多帶圖靈機與基本的圖靈機等價。 證明要點： 對一個k帶圖靈機，用一條具有2k道的雙向無窮帶圖靈機M，實現(xiàn)對這個k帶圖靈機M的模擬。 對應(yīng)M的每一條帶，M用兩個道來實現(xiàn)模擬。其中一條道用來存放對應(yīng)的帶的內(nèi)容，另一條道專門用來標(biāo)記對應(yīng)帶上的讀頭所在的位置。,73,2.2.3 不確定的圖靈機,不確定圖靈機與基本圖靈

35、機的區(qū)別是對于任意的(q，X)Q， (q，X)=(q1，Y1，D1)，(q2，Y2，D2)，(qk，Yk，Dk) Dj為讀頭的移動方向。即DjR，L。 表示M在狀態(tài)q，讀到X時，可以有選擇地進入狀態(tài)qj，印刷字符Yj，按Dj移動讀頭 L(M)=w | w*且ID1*IDn，且IDn含M的終止?fàn)顟B(tài)。,74,2.2.3 不確定的圖靈機,定理 2-3 不確定的圖靈機與基本的圖靈機等價 證明要點： 讓等價的基本圖靈機M 具有3條帶。 第1條帶用來存放輸入。 第2條帶上系統(tǒng)地生成M的各種可能的移動序列 M在第3條帶上按照第2條帶上給出的移動系列處理輸入串，如果成功，則接受之，如果不成功，則在第2條帶上生

36、成下一個可能的移動系列，開始新一輪的“試處理”。,75,2.2.4 多維圖靈機,多維圖靈機(multi-dimensional Turing machine) 讀頭可以沿著多個維移動。 k維圖靈機(k-dimensional Turing machine) 圖靈機可以沿著k維移動。 k維圖靈機的帶由k維陣列組成，而且在所有的2k個方向上都是無窮的，它的讀頭可以向著2k個方向中的任一個移動。,76,2.2.4 多維圖靈機,定理 2-4 多維圖靈機與基本圖靈機等價。 用一維的形式表示k維的內(nèi)容，就像多維數(shù)組在計算機的內(nèi)存中都被按照一維的形式實現(xiàn)存儲一樣。 段(Segment)用來表是一維上的內(nèi)容。

37、 用#作為段分割符。 用作該字符串的開始標(biāo)志，$用作該字符串的結(jié)束標(biāo)志。,77,基本圖靈機模擬2維圖靈機,78,基本圖靈機模擬2維圖靈機,Ba1a2a3a4BBBBBB # Ba5Ba6a7a8a9a10BBB # Ba11BBBBa12Ba13Ba14 # a15 a16BBBBBBBB a16# BBB a17BBBBBa18B # a19a20BBBBBBBBB # BBBBBBBBBBa21$,79,2.2.5 其他圖靈機,1. 多頭TM 2. 離線TM 3. 作為枚舉器的TM 4. 多棧機 5. 計數(shù)機 6. Church-Turing論題與隨機存取機,80,1. 多頭圖靈機,多頭圖

38、靈機(multi-head Turing machine) 指在一條帶上有多個讀頭，它們受M的有窮控制器的統(tǒng)一控制，M根據(jù)當(dāng)前的狀態(tài)和這多個頭當(dāng)前讀到的字符確定要執(zhí)行的移動。在M的每個動作中，各個讀頭所印刷的字符和所移動的方向都可以是相互獨立的。,81,1. 多頭圖靈機,定理 2-5 多頭圖靈與基本的圖靈機等價。 可以用一條具有k+1個道的基本圖靈機來模擬一個具有k個頭的圖靈（k頭圖靈機）。其中一個道用來存放原輸入帶上的內(nèi)容，其余k個道分別用來作為k個讀頭位置的標(biāo)示。,82,2. 離線圖靈機,離線圖靈機(off-line Turing machine) 有一條輸入帶是只讀帶(read-only

39、 tape)的多帶圖靈機。 符號和$用來限定它的輸入串存放區(qū)域，在左邊，$在右邊。 不允許該帶上的讀頭移出由和$限定的區(qū)域離線的圖靈機。 如果只允許只讀帶上的讀頭從左向右移動，則稱之為在線圖靈機(on-line Turing machine)。,83,2. 離線圖靈機,定理 2-6 離線圖靈機與基本的圖靈機等價。 證明要點：讓模擬M的離線圖靈機比M多一條帶，并且用這多出來的帶復(fù)制M的輸入串。然后將這條帶看作是M的輸入帶，模擬M進行相應(yīng)的處理。,84,3. 作為枚舉器的圖靈機,作為枚舉器的圖靈機(Turing machine as enumerator) 多帶圖靈機，其中有一條帶專門作為輸出帶，

40、用來記錄產(chǎn)生語言的每一個句子。 在枚舉器中，一旦一個字符被寫在了輸出帶上，它就不能被更改。如果該帶上的讀頭的正常移動方向是向右移動的話，這個帶上的讀頭是不允許向左移動的。 如果這個語言有無窮多個句子，則它將永不停機。它每產(chǎn)生一個句子，就在其后打印一個分割符“#”。 枚舉器產(chǎn)生的語言記為G(M)。,85,3. 作為枚舉器的圖靈機,規(guī)范的順序(canonical order) 定理 2-7 L為遞歸可枚舉語言的充分必要條件是存在一個圖靈機 M，使得L=G(M)。 定理 2-8 一個語言L為遞歸語言的充分必要條件是存在一個圖靈機M，使得L=G(M)，并且L是被M按照規(guī)范順序產(chǎn)生的。,86,4. 多棧

41、機,多棧機(multi-stack machines)是一個擁有一條只讀輸入帶和多條存儲帶的不確定圖靈機。 多棧機的只讀帶上的讀頭不能左移。 存儲帶上的讀頭可以向左和向右移動。 右移時，一般都在當(dāng)前注視的帶方格上印刷一個非空白字符。 左移時，必須在當(dāng)前注視的帶方格中印刷空白字符B。 一個確定的雙棧機(double stack machines)是一個確定的圖靈機，它具有一條只讀的輸入帶和兩條存儲帶。存儲帶上的讀頭左移時，只能印刷空白符號B 。,87,4. 多棧機,下推自動機是一種非確定的多帶圖靈機。它有一條只讀的輸入帶，一條存儲帶。 定理 2-9 一個任意的單帶圖靈機可以被一個確定的雙棧機模擬

42、。,88,5. 計數(shù)機,計數(shù)機(counter machine) 有一條只讀輸入帶和若干個用于計數(shù)的單向無窮帶的離線圖靈機。 擁有n個用于計數(shù)帶的計數(shù)機被稱為n計數(shù)機。 用于計數(shù)的帶上僅有兩種字符，一個為相當(dāng)于是作為棧底符號的Z，該字符也可以看作是計數(shù)帶的首符號，它僅出現(xiàn)在計數(shù)帶的最左端；另一個就是空白符B。這個帶上所記的數(shù)就是從Z開始到讀頭當(dāng)前位置所含的B的個數(shù)。 定理 2-10 圖靈機可以被一個雙計數(shù)機模擬。,89,6.丘奇-圖靈論題與隨機存取機,對于任何可以用有效算法解決的問題，都存在解決此問題的圖靈機。 隨機存取機(random access machine，RAM)含有無窮多個存儲單

43、元，這些存儲單元被按照0、1、2、進行編號，每個存儲單元可以存放一個任意的整數(shù)；有窮個能夠保存任意整數(shù)的算術(shù)寄存器。這些整數(shù)可以被譯碼成通常的各類計算機指令。 定理 2-11如果RAM的基本指令都能用圖靈機來實現(xiàn)，那么就可以用圖靈機實現(xiàn)RAM。,90,2.3 通用圖靈機,通用圖靈機(universal Turing machine) 實現(xiàn)對所有圖靈機的模擬。 編碼系統(tǒng) 它可以在實現(xiàn)對圖靈機的表示的同時，實現(xiàn)對該TM處理的句子的表示。 用0和1對這些除空白符以外的其他的帶符號進行編碼。同時也可以用0和1對圖靈機的移動函數(shù)進行編碼。,91,2.3 通用圖靈機,M=(q1, q2, , qn, 0，

44、1, 0，1，B, ,q1 , B , q2) 用X1、X2、X3分別表示0、1、B，用D1、D2分別表示R、L。 (qi, Xj)=(qk , Xl, Dm)可以用0i10j10k10l10m表示。,92,2.3 通用圖靈機,圖靈機M可用 111 code1 11 code2 11 11 coder 111 codet 是動作(qi, Xj)=(qk , Xl, Dm)的形如0i10j10k10l10m的編碼。 圖靈機M和它的輸入串w則可以表示成 111 code1 11 code2 11 11 coder 111w 按照規(guī)范順序分別對表示圖靈機的符號行和表示輸入的符號行進行排序。,93,2

45、.3 通用圖靈機,Ld=w | w是第j個句子，并且第j個圖靈機不接受它不是遞歸可枚舉語言。 通用語言(universal language) Lu= | M接受w 為如下形式的串，表示圖靈機M=(q1, q2, , qn, 0，1, 0，1，B, ,q1 , B , q2)和它的輸入串w。 111 code1 11 code2 11 11 coder 111w,94,2.3 通用圖靈機,例 2-12 設(shè)圖靈機 M2=( q1, q2, q3, q4, 0, 1, 0, 1, B, , q4 , B ,q3)，其中的定義如下: (q4, 0)= (q4, 0, R) (q4, 1)= (q1, 1, R) (q1, 0)= (q1, 0, R) (q1, 1)= (q2, 1, R) (q2, 0)= (q2, 0, R) (q2, 1)= (q3, 1, R),95,2.3 通用圖靈機,編碼為 1110000101000010101100001001010010110101010101101001001001