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

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

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

3、圖靈機(jī)4.4圖靈機(jī)可計(jì)算性74.1 圖靈機(jī)模型 84.1 圖靈機(jī)模型圖靈機(jī)模型定義定義4-1 圖靈機(jī)M = ( K, , , , q0, B,F)，其中 K是有窮的狀態(tài)集合； 是所允許的帶符號(hào)集合； B ，是空白符； ，B ，是輸入字符集合； F K，是終止?fàn)顟B(tài)集合。，是終止?fàn)顟B(tài)集合。 q0K, 是初始狀態(tài)；是初始狀態(tài)； 94.1 圖靈機(jī)模型圖靈機(jī)模型：KKL,R,S是圖靈機(jī)的動(dòng)作(狀態(tài)轉(zhuǎn)移)函數(shù)，這里L(fēng)表示讀頭左移一格；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.104.1 圖靈機(jī)模型圖靈機(jī)

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

5、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 *ID2134.1 圖靈機(jī)模型圖靈機(jī)模型n定義定義4-4 對(duì)于圖靈機(jī)M = ( K, , , , q0, B, F)，定義圖靈機(jī)接受的語(yǔ)言集 L(M) 為L(zhǎng)(M)=w|w* u0 u v q qf(u0*u*v* qKqf F q0w*u0qB*uqfv)144.1 圖靈機(jī)模型圖靈機(jī)模型n【例【例4-1】設(shè)計(jì)一個(gè)圖靈機(jī)，使得】設(shè)計(jì)一個(gè)圖靈機(jī)，使得 L(M) = 0 n1 n | n1。設(shè)計(jì)思路設(shè)計(jì)思路: 在帶上每當(dāng)將一個(gè)在帶

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

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

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

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

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

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

12、制到一進(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ù)制一遍。例如：1001的一進(jìn)制數(shù)計(jì)算過(guò)程。304.2.2 多帶圖靈機(jī)314.2.2 多帶圖靈機(jī)定理定理4-2 如果一個(gè)語(yǔ)言L被一個(gè)多帶圖靈機(jī)接受，它就能被一個(gè)單帶圖靈機(jī)接受。 324.2.3 非確定圖靈機(jī)【例【例4-8】下面的圖靈機(jī)就是不確定圖靈機(jī)。無(wú)向圖G中，從a出發(fā)合法路徑判定的不確定型圖靈機(jī)。334.2.3 非確定圖靈機(jī)n非確定

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

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

15、動(dòng)它的讀頭，開(kāi)始時(shí)，輸入沿著方向上移動(dòng)它的讀頭，開(kāi)始時(shí)，輸入沿著一個(gè)軸排列，讀頭在輸入的左端。一個(gè)軸排列，讀頭在輸入的左端。374.2.6 離線圖靈機(jī)定理定理4-5 如果L被一個(gè)二維圖靈機(jī)M1接受，那么L將被一個(gè)一維圖靈機(jī)M2接受。384.2.7 圖靈機(jī)的組合394.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è)的左邊全變?yōu)锽時(shí)，帶上就為10n10mn，再抹去10n1，帶上就剩0mn，即為所求。設(shè)計(jì)Copy子程序 這個(gè)子程序完成

16、在第二個(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。 404.2.7 圖靈機(jī)的組合設(shè)計(jì)主 MM= q0,q6,q7,q8,q9,q10,q11,q12,q13,0,1,0,1,2,B,q0, B, q13)開(kāi)始ID為q00m10n1，進(jìn)入Copy入口ID為B0m-11q10n1，為此，(q0,0)=(q6,B,R)(q6,0)=(q6,0,R) (q6,1)

17、=(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)善后處理：Bm1q50n10mn414.2.8 枚舉器424.2.8 枚舉器定理定理4-6 一個(gè)語(yǔ)言是圖靈可識(shí)別的，當(dāng)且僅當(dāng)有枚舉器枚舉它。證明：首先證明如果有枚舉器E枚舉語(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ò)的那

18、些串?，F(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)行。434.3 通用圖靈機(jī)通用圖靈機(jī)() 緩沖域帶的最左面是標(biāo)記符，的右邊是|K|+|+2個(gè)單元構(gòu)成的緩沖（|K|、|分別是狀態(tài)集和字母集的元素?cái)?shù)目）。() 的描述字域緩沖區(qū)域右邊緊接的是的描述字dM，以為開(kāi)始標(biāo)志，以個(gè)結(jié)束。對(duì)于轉(zhuǎn)

19、移函數(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() 的輸入描述域的描述字域的右邊存放的是輸入串的編碼：用字母的序號(hào)表示該字母，并用分隔。該域以為起始標(biāo)志。如輸入為111，則該串表示為：110110110444.3 通用圖靈機(jī)通用圖靈

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

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

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

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

24、(x1, x2, ,xn)是部分圖是部分圖靈可計(jì)算的，若有一圖靈程序靈可計(jì)算的，若有一圖靈程序P，使得，使得P(x1, x2, ,xn) = f(x1, x2, ,xn)n其中其中P(x1, x2, ,xn)是是P對(duì)應(yīng)的函數(shù)，對(duì)應(yīng)的函數(shù)，“=”表示若有定義，則值相等；否則，均表示若有定義，則值相等；否則，均無(wú)定義。無(wú)定義。504.4.1 圖靈可計(jì)算性函數(shù)圖靈可計(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ù)。514.4.1 圖靈可計(jì)算

25、性函數(shù)圖靈可計(jì)算性函數(shù)524.4.1 圖靈可計(jì)算性函數(shù)圖靈可計(jì)算性函數(shù)定理定理4-7 設(shè)設(shè)g1, g2, gm是是n元圖靈可計(jì)元圖靈可計(jì)算函數(shù)，算函數(shù)，h是是m元圖靈可計(jì)算函數(shù)，則復(fù)合元圖靈可計(jì)算函數(shù)，則復(fù)合函數(shù)函數(shù)f=h (g1,g2,gm)也是圖靈可計(jì)算的。也是圖靈可計(jì)算的。534.4.2 圖靈機(jī)的枚舉定理圖靈機(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)544.4.2 圖靈機(jī)的枚舉定理圖靈機(jī)的枚舉定理定理定理4-8 枚舉定理枚舉定理 對(duì)于每個(gè)自然數(shù)z，部分函數(shù)(n)(z,x1,x2,xn)是(部分)圖靈可計(jì)算函數(shù)。證明它能枚舉所