計(jì)算理論第4章圖靈機(jī).ppt

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

2、 左線性文法 ABx，Cy x,yT* 法,4,Overview,0型語(yǔ)言 圖靈機(jī) 1型語(yǔ)言(CSL) 線性界限自動(dòng)機(jī) 2型語(yǔ)言(CFL) 下推自動(dòng)機(jī) 3型語(yǔ)言(正規(guī)集)有限自動(dòng)機(jī),5,Overview,圖靈機(jī)所定義的語(yǔ)言類(lèi)-遞歸可枚舉集合 圖靈機(jī)所計(jì)算的整數(shù)函數(shù)類(lèi)-部分遞歸函數(shù) 以圖靈機(jī)為模型,研究問(wèn)題的可計(jì)算性，即確定該問(wèn)題是可計(jì)算的、部分可計(jì)算的，還是不可計(jì)算的。,6,Overview,4.1 圖靈機(jī)模型 4.2 圖靈機(jī)的變化和組合 4.3 通用圖靈機(jī) 4.4圖靈機(jī)可計(jì)算性,7,4.1 圖靈機(jī)模型,8,4.1 圖靈機(jī)模型,定義4-1 圖靈機(jī)M = ( K, , , , q0, B,F)，

3、 其中 K是有窮的狀態(tài)集合； 是所允許的帶符號(hào)集合； B ，是空白符； ，B ，是輸入字符集合； F K，是終止?fàn)顟B(tài)集合。 q0K, 是初始狀態(tài)；,9,4.1 圖靈機(jī)模型,：KKL,R,S 是圖靈機(jī)的動(dòng)作(狀態(tài)轉(zhuǎn)移)函數(shù)，這里 L表示讀頭左移一格； R表示讀頭右移一格； S表示讀頭不動(dòng)； (q,a)=(p,b,z) 表示狀態(tài)q下讀頭所讀符號(hào)為a時(shí)，狀態(tài)轉(zhuǎn)移為p,讀頭符號(hào)變?yōu)閎，同時(shí)讀頭變化為z.,10,4.1 圖靈機(jī)模型,定義4-2 設(shè)當(dāng)前帶上字符串為x1x2 xn，當(dāng)前狀態(tài)為q，讀頭正在讀xi ，圖靈機(jī)的瞬時(shí)描述ID 為 x1x2 xi-1 q xi xn,11,4.1 圖靈機(jī)模型,定義4-

4、3 設(shè)當(dāng)前的瞬時(shí)描述 ID1= x1x2 xi-1 q xi xn 若有(q, x i) = (p, y, L)，則圖靈機(jī)瞬時(shí)描述變?yōu)?ID2 = x 1x 2 x i-2p x i-1 y x i+1 x n； 若有 (q, x i) = (p, y, R)，則圖靈機(jī)瞬時(shí)描述變?yōu)?ID2 = x1x2 xi-1 y pxi+1 xn。,12,4.1 圖靈機(jī)模型,定義4-3 瞬時(shí)描述ID1經(jīng)過(guò)一步變?yōu)樗矔r(shí)描述ID2，稱(chēng)ID1與ID2具有一步變化關(guān)系，表示為 ID1ID2 若ID1經(jīng)過(guò)n步變?yōu)镮D2(n0)，即有 ID1ID ID2 稱(chēng)ID1與ID2具有多步變化關(guān)系，簡(jiǎn)記為 ID1 *ID2,1

5、3,4.1 圖靈機(jī)模型,定義4-4 對(duì)于圖靈機(jī)M = ( K, , , , q0, B, F)，定義圖靈機(jī)接受的語(yǔ)言集 L(M) 為 L(M)=w|w* u0 u v q qf(u0*u*v* qKqf F q0w*u0qB*uqfv),14,4.1 圖靈機(jī)模型,【例4-1】設(shè)計(jì)一個(gè)圖靈機(jī)，使得 L(M) = 0 n1 n | n1。 設(shè)計(jì)思路: 在帶上每當(dāng)將一個(gè)0變?yōu)閄，就把一個(gè)1變?yōu)閅。當(dāng)將所有的0變?yōu)閄時(shí)，恰將所有的1變?yōu)閅，這個(gè)串就是合法的，最后將X、Y分別還原為0、1。,15,4.1 圖靈機(jī)模型,16,4.1 圖靈機(jī)模型,【例4-2】 設(shè)計(jì)一個(gè)圖靈機(jī)，使之接受 L(M) = wcw

6、| w a,b* 設(shè)計(jì)思路：在c左側(cè)，從左至右逐一字符，用狀態(tài)記下它并標(biāo)志該符號(hào)為已處理符號(hào)，移至c右側(cè)對(duì)應(yīng)位置后，判斷是否是相同符號(hào)。若相同，再返回c左側(cè)循環(huán)，直至所有符號(hào)比較完畢。最后將標(biāo)志符號(hào)修改回原符號(hào)。在設(shè)計(jì)時(shí)，特別注意用狀態(tài)存貯符號(hào)的方法，這是圖靈機(jī)設(shè)計(jì)的重要方法之一。,17,4.1 圖靈機(jī)模型,18,4.1 圖靈機(jī)模型,【例4-3】設(shè)計(jì)一個(gè)圖靈機(jī)，計(jì)算自然數(shù)n的以2為底的對(duì)數(shù)。 用一進(jìn)制表示輸入和輸出值。an表示輸入n, bm表示輸出m. 設(shè)計(jì)思路：從左到右掃描帶，把所碰到的a劃掉一個(gè)，留一個(gè)，并將計(jì)數(shù)器加1。重復(fù)此過(guò)程，直至a不復(fù)存在。這里，用字符c表示劃掉的字符。,19,4.

7、1圖靈機(jī)模型,20,4.1 圖靈機(jī)模型,【例4-4】設(shè)計(jì)一個(gè)圖靈機(jī)，計(jì)算二個(gè)自然數(shù)m、n的減法： 設(shè)計(jì)時(shí)，整數(shù)n用0n表示。開(kāi)始時(shí)，帶上符號(hào)為 0m10n，結(jié)束時(shí)，帶上符號(hào)為0。每當(dāng)在1的左邊將一個(gè)0改變?yōu)锽，就在1的右邊將一個(gè)0改為1，若1的右邊無(wú)0時(shí)，再將左邊改為B的0恢復(fù)回來(lái)。,m-n 若mn mn= 0 否則,21,4.1 圖靈機(jī)模型,R,22,4.1 圖靈機(jī)模型,【例4-5】 設(shè)計(jì)圖靈機(jī)實(shí)現(xiàn)數(shù)字從一進(jìn)制表示到二進(jìn)制表示的轉(zhuǎn)換。 這個(gè)圖靈機(jī)的設(shè)計(jì)可以仿例4-3 ，不同在于每次循環(huán)時(shí)，要保留除以2的余數(shù)作為當(dāng)前二進(jìn)制位的值。注意這里首先計(jì)算出的是二進(jìn)制的低位值，所以要將結(jié)果不斷右移以插入

8、新生成的位，生成的結(jié)果是低位在右端。初始時(shí)，整數(shù)n用an表示，結(jié)束時(shí)，帶上是0、1構(gòu)成的二進(jìn)制數(shù)。,23,4.1 圖靈機(jī)模型,R,24,4.2 圖靈機(jī)的變化和組合,4.2.1 雙向無(wú)窮帶圖靈機(jī) 4.2.2 多帶圖靈機(jī) 4.2.3 非確定圖靈機(jī) 4.2.4 多頭圖靈機(jī) 4.2.5 多維圖靈機(jī) 4.2.6 離線圖靈機(jī) 4.2.7 圖靈機(jī)的組合 4.2.8 枚舉器,25,4.2.1雙向無(wú)窮帶圖靈機(jī),定理4-1 L被一個(gè)具有雙向無(wú)窮帶的圖靈機(jī)識(shí)別，當(dāng)且僅當(dāng)它被一個(gè)單向無(wú)限帶的圖靈機(jī)識(shí)別。 證明：?jiǎn)蜗驘o(wú)限TM模擬雙向無(wú)限TM，采用多道技術(shù)。,26,4.2.2 多帶圖靈機(jī),27,4.2.2 多帶圖靈機(jī),【

9、例4-6】設(shè)計(jì)一個(gè)二帶圖靈機(jī)，使得 T(M)= | 0,1*。 這個(gè)問(wèn)題的關(guān)鍵是比較字符串前后兩個(gè)部分，為此，首先要對(duì)帶上字符串計(jì)數(shù)：每二元素計(jì)數(shù)加1，按計(jì)數(shù)值將字符串分為前后兩個(gè)部分，并將它們分別存放于不同帶上，然后進(jìn)行比較。,28,4.2.2 多帶圖靈機(jī),29,4.2.2 多帶圖靈機(jī),【例4-7】 設(shè)計(jì)二帶圖靈機(jī)，實(shí)現(xiàn)二進(jìn)制到一進(jìn)制的轉(zhuǎn)換。 設(shè)這個(gè)圖靈機(jī)為M7，其第一帶用作輸入帶，第二帶用作輸出帶。設(shè)計(jì)思路是從左到右掃描輸入帶上的二進(jìn)制字符，并使用公式r*2+b生成輸出帶上一進(jìn)制數(shù)，其中r是當(dāng)前輸出帶上的一進(jìn)制數(shù)，b是當(dāng)前輸入帶上掃描的字符，這里的r*2就是將原輸出帶上的一進(jìn)制數(shù)r復(fù)制一遍

10、。例如：1001的一進(jìn)制數(shù)計(jì)算過(guò)程。,30,4.2.2 多帶圖靈機(jī),31,4.2.2 多帶圖靈機(jī),定理4-2 如果一個(gè)語(yǔ)言L被一個(gè)多帶圖靈機(jī)接受，它就能被一個(gè)單帶圖靈機(jī)接受。,32,4.2.3 非確定圖靈機(jī),【例4-8】下面的圖靈機(jī)就是不確定圖靈機(jī)。無(wú)向圖G中，從a出發(fā)合法路徑判定的不確定型圖靈機(jī)。,33,4.2.3 非確定圖靈機(jī),非確定圖靈機(jī)由一個(gè)有窮控制器、一條帶和一個(gè)讀頭組成。對(duì)于一個(gè)給定的狀態(tài)和被讀頭掃描的帶符號(hào)，機(jī)器的下一個(gè)動(dòng)作將有有窮個(gè)選擇。 設(shè)一個(gè)非確定圖靈機(jī) M1=( K, ,q0, B, F)，除轉(zhuǎn)移函數(shù)外，其它同一般圖靈機(jī)的定義。轉(zhuǎn)移函數(shù)仍是從K到KL,R,S上的映射，但它

11、可能有多個(gè)映射的像,即存在qK, a, (q,a)= (p1, b1, c1) (q,a)= (p2, b2, c2) (q,a)= (pr, br, cr),34,4.2.3 非確定圖靈機(jī),定理4-3 如果語(yǔ)言L被一個(gè)非確定圖靈機(jī)M1接受，則L將被某個(gè)確定圖靈機(jī)M2接受。,35,4.2.4 多頭圖靈機(jī),一個(gè)k頭圖靈機(jī)有k個(gè)讀頭，一個(gè)控制器和一條帶，讀頭由1到k編號(hào)，圖靈機(jī)的一個(gè)動(dòng)作由當(dāng)前狀態(tài)和被每個(gè)讀頭所掃描的符號(hào)。在一個(gè)動(dòng)作中，每個(gè)讀頭獨(dú)立地左移、右移或不動(dòng)。 定理4-4 如果L被某個(gè)k個(gè)讀頭的圖靈機(jī)接受，則它能被一個(gè)單頭圖靈機(jī)接受。,36,4.2.5 多維圖靈機(jī),多維圖靈機(jī)具有通常的有限

12、控制器，但帶卻由k維單元陣列組成。這里，在所有2k個(gè)方向上（k個(gè)軸，每軸正、負(fù)兩個(gè)方向），都是無(wú)限的，根據(jù)狀態(tài)和掃視的符號(hào)，該裝置改變狀態(tài)，打印一個(gè)新的符號(hào)，在2k個(gè)方向上移動(dòng)它的讀頭，開(kāi)始時(shí)，輸入沿著一個(gè)軸排列，讀頭在輸入的左端。,37,4.2.6 離線圖靈機(jī),定理4-5 如果L被一個(gè)二維圖靈機(jī)M1接受，那么L將被一個(gè)一維圖靈機(jī)M2接受。,38,4.2.7 圖靈機(jī)的組合,39,4.2.7 圖靈機(jī)的組合,【例4-9】 設(shè)計(jì)一個(gè)TM ，完成乘法運(yùn)算mn。開(kāi)始時(shí)帶上符號(hào)為：0m10n1，結(jié)束時(shí)帶上符號(hào)為0mn，用子程序調(diào)用的方式完成。 設(shè)計(jì)思想是：每當(dāng)抹去左邊一個(gè)，就在第二個(gè)后面拷貝n個(gè)。當(dāng)?shù)谝粋€(gè)

13、的左邊全變?yōu)锽時(shí)，帶上就為10n10mn，再抹去10n1，帶上就剩0mn，即為所求。 設(shè)計(jì)Copy子程序 這個(gè)子程序完成在第二個(gè)拷貝n個(gè)的操作。 第1次被調(diào)用開(kāi)始ID：Bm-11q10n1 結(jié)束ID：Bm-11q50n10n 第i次被調(diào)用開(kāi)始ID：Bim-i1q10n10(i-1)n 結(jié)束ID：Bim-i1q50n10in 在拷貝時(shí)，每當(dāng)將一個(gè)變成，就在末尾寫(xiě)個(gè)。當(dāng)0n變?yōu)?n時(shí)，就已在右邊加了0n。再將2變?yōu)?n。,40,4.2.7 圖靈機(jī)的組合,設(shè)計(jì)主 M M= q0,q6,q7,q8,q9,q10,q11,q12,q13,0,1,0,1,2,B,q0, B, q13) 開(kāi)始ID為q00m

14、10n1，進(jìn)入Copy入口ID為B0m-11q10n1，為此， (q0,0)=(q6,B,R) (q6,0)=(q6,0,R) (q6,1)=(q1,1,R) 從Copy結(jié)束時(shí)的ID，進(jìn)入主TM的開(kāi)始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) 善后處理：Bm1q50n10mn,41,4.2.8 枚舉器,42,4.2.8 枚舉器,定理4-6 一個(gè)語(yǔ)言是圖靈可識(shí)別的，當(dāng)且僅當(dāng)有枚舉器枚舉它。 證明：首先證明如果有枚舉器E

15、枚舉語(yǔ)言L，則存在圖靈機(jī)M識(shí)別L。構(gòu)造M如下： 對(duì)于任意輸入串w，運(yùn)行E。每當(dāng)E輸出一個(gè)串時(shí)，與w比較，若相等，接受w，并停機(jī)。 顯然，M接受在E輸出序列中出現(xiàn)過(guò)的那些串。 現(xiàn)在證明若有圖靈機(jī)M識(shí)別語(yǔ)言L，則有枚舉器E枚舉L。 設(shè)L=w1，w2，w3，構(gòu)造E如下： 對(duì)i=1,2,3,執(zhí)行如下步驟 （1）對(duì)w1，w2，w3，, wi中的每一串，讓M以其作為輸入運(yùn)行i步。 （2）若在這個(gè)計(jì)算中，M接受wj，則打印wj， M接受w，它最終將出現(xiàn)在E的枚舉打印中。事實(shí)上，它可能在E的列表在出現(xiàn)無(wú)限多次，因?yàn)槊恳淮沃貜?fù)運(yùn)行，M在每一個(gè)串上都從頭開(kāi)始運(yùn)行。,43,4.3 通用圖靈機(jī),() 緩沖域帶的最左面

16、是標(biāo)記符，的右邊是|K|+|+2個(gè)單元構(gòu)成的緩沖（|K|、|分別是狀態(tài)集和字母集的元素?cái)?shù)目）。 () 的描述字域緩沖區(qū)域右邊緊接的是的描述字dM，以為開(kāi)始標(biāo)志，以個(gè)結(jié)束。對(duì)于轉(zhuǎn)移函數(shù) (q,a)=(q,a,d)， 我們用五元組表示為(q, a, q, a, d)，將順序調(diào)整為(q, a, a, d, q)。 dM就是由這樣的五元組組成的序列。對(duì)于每個(gè)五元組中的狀態(tài)和字符，我們用其序號(hào)的一進(jìn)表示，其間用分隔，五元組間用個(gè)分隔。例如：若有(q,)=(q,)，表示成上面定義的五元組是(q,，,，q)，再用其序號(hào)表示為(2,0,2,0,3)，在U2的帶上表示為 011101011101011110 (

17、) 的輸入描述域的描述字域的右邊存放的是輸入串的編碼：用字母的序號(hào)表示該字母，并用分隔。該域以為起始標(biāo)志。如輸入為111，則該串表示為： 110110110,44,4.3 通用圖靈機(jī),UTM U2模擬具體步驟如下： 步0 將讀頭置于描述字區(qū)域的開(kāi)始符號(hào)上。此時(shí)緩沖區(qū)域是； 步1U2復(fù)寫(xiě)標(biāo)記或后面的狀態(tài)到緩沖域的初始位置，然后在其后面加一個(gè)輔助符號(hào)，讀寫(xiě)頭右移到符號(hào)； 步2 U2復(fù)寫(xiě)后面的初始帶模式到緩沖區(qū)部分，即在之后； 步3 U2將改為0，現(xiàn)緩沖區(qū)中包含當(dāng)前狀態(tài)和掃描的字母； 步4對(duì)描述字域進(jìn)行搜索，查看前兩項(xiàng)匹配的元組。若所有的五元組都不匹配，則表明停機(jī)，U2也停機(jī)。若找到一個(gè)匹配的五元組

18、，標(biāo)記、表示正在比較的狀態(tài)或符號(hào)；,45,4.3 通用圖靈機(jī),步5(找到匹配的五元組)刪去緩沖區(qū)的內(nèi)容，并把標(biāo)記右移一個(gè)符號(hào)，使處于該五元組的新符號(hào)的前面； 步6用新符號(hào)代替標(biāo)記后面的符號(hào)(可能需擴(kuò)充或壓縮原輸入描述域)，U2將標(biāo)記右移至五元組的方向分量前； 步7 U2計(jì)數(shù)方向分量中的個(gè)數(shù)，然后按要求向左或向右移動(dòng)標(biāo)記。若向左離開(kāi)了輸入串，則U2停機(jī)；若向右離開(kāi)了輸入串，U2必須添加一個(gè)表示下一個(gè)方格的新的“”串。當(dāng)前U2描述字域標(biāo)記后面不是結(jié)束狀態(tài)，則轉(zhuǎn)至步1；否則接受輸入串并停機(jī)。,46,4.3 通用圖靈機(jī),47,4.3 通用圖靈機(jī),對(duì)于任何一個(gè)圖靈機(jī)M，都有一個(gè)確定的描述字dM，如在例4

19、-10中dM=1010101101100101110111010111001101101101101 將它看作一個(gè)二進(jìn)制數(shù)，實(shí)質(zhì)上，它是一個(gè)整數(shù)，因此按這 種表示，任何一個(gè)圖靈機(jī)都和一個(gè)整數(shù)相對(duì)應(yīng)，這個(gè)整數(shù)，稱(chēng)為圖靈機(jī)的標(biāo)記。,48,4.4圖靈可計(jì)算性,4.4.1 圖靈可計(jì)算性函數(shù) 4.4.2 圖靈機(jī)的枚舉定理 4.4.3 圖靈機(jī)的計(jì)算限界,49,4.4.1 圖靈可計(jì)算性函數(shù),定義4-5 函數(shù)f(x1, x2, ,xn)是部分圖靈可計(jì)算的，若有一圖靈程序P，使得 P(x1, x2, ,xn) = f(x1, x2, ,xn) 其中P(x1, x2, ,xn)是P對(duì)應(yīng)的函數(shù)，“=”表示若有定義，

20、則值相等；否則，均無(wú)定義。,50,4.4.1 圖靈可計(jì)算性函數(shù),定義4-6 函數(shù)f(x1, x2, ,xn)是全函數(shù)，若它對(duì)一切x1, x2, ,xn都有定義。 定義4-7 函數(shù)f(x1, x2, ,xn)是圖靈可計(jì)算函數(shù)，若它是部分圖靈可計(jì)算的而且是全函數(shù)。,51,4.4.1 圖靈可計(jì)算性函數(shù),52,4.4.1 圖靈可計(jì)算性函數(shù),定理4-7 設(shè)g1, g2, gm是n元圖靈可計(jì)算函數(shù)，h是m元圖靈可計(jì)算函數(shù)，則復(fù)合函數(shù) f=h (g1,g2,gm) 也是圖靈可計(jì)算的。,53,4.4.2 圖靈機(jī)的枚舉定理,1圖靈機(jī)的標(biāo)記 2圖靈可計(jì)算的重要定理 定義4-8 若z是一個(gè)圖靈機(jī)M的標(biāo)記，并且M計(jì)算部分函數(shù)g(x1,x2,xn)，則定義函數(shù)(n) 為 (n)(z,x1,x2,xn)= g(x1,x2,xn),54,4.4.2 圖靈機(jī)的枚舉定理,定理4-8 枚舉定理 對(duì)于每個(gè)自然數(shù)z，部分函數(shù)(n)(z,x1,x2,xn)是(部分)圖靈可計(jì)算函數(shù)。 證