1、形式語(yǔ)言與自動(dòng)機(jī)理論Formal Languages and Automata Theory,蔣宗禮,課程目的和基本要求,課程性質(zhì) 技術(shù)基礎(chǔ) 基礎(chǔ)知識(shí)要求 數(shù)學(xué)分析（或者高等數(shù)學(xué)），離散數(shù)學(xué) 主要特點(diǎn) 抽象和形式化 理論證明和構(gòu)造性 基本模型的建立與性質(zhì),課程目的和基本要求,本專(zhuān)業(yè)人員4種基本的專(zhuān)業(yè)能力 計(jì)算思維能力 算法的設(shè)計(jì)與分析能力 程序設(shè)計(jì)和實(shí)現(xiàn)能力 計(jì)算機(jī)軟硬件系統(tǒng)的認(rèn)知、分析、設(shè)計(jì)與應(yīng)用能力 計(jì)算思維能力 邏輯思維能力和抽象思維能力 構(gòu)造模型對(duì)問(wèn)題進(jìn)行形式化描述 理解和處理形式模型,課程目的和基本要求,知識(shí) 掌握正則語(yǔ)言、下文無(wú)關(guān)語(yǔ)言的文法、識(shí)別模型及其基本性質(zhì)、圖靈機(jī)的基本知識(shí)。

2、 能力 培養(yǎng)學(xué)生的形式化描述和抽象思維能力。 使學(xué)生了解和初步掌握“問(wèn)題、形式化描述、自動(dòng)化（計(jì)算機(jī)化）”這一最典型的計(jì)算機(jī)問(wèn)題求解思路。,主要內(nèi)容,語(yǔ)言的文法描述。 RL RG、 FA、RE、RL的性質(zhì) 。 CFL CFG(CNF、GNF)、PDA、CFL的性質(zhì)。 TM 基本TM、構(gòu)造技術(shù)、TM的修改。 CSL CSG、LBA。,教材及主要參考書(shū)目,蔣宗禮，姜守旭. 形式語(yǔ)言與自動(dòng)機(jī)理論. 北京：清華大學(xué)出版社，2003年 John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory, L

3、anguages, and Computation (2nd Edition). Addison-Wesley Publishing Company, 2001 John E Hopcroft, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, 1979,第9章 圖靈機(jī),圖靈機(jī)(Turing machine)是由圖靈(Alan MathisomTuring)在1936年提出的，它是一個(gè)通用的計(jì)算模型。 通過(guò)研究TM，來(lái)

4、研究遞歸可枚舉集(recursively enumerable set)和部分地歸函數(shù)(partial recursive function)。 對(duì)算法和可計(jì)算性進(jìn)行研究提供形式化描述工具。,第9章 圖靈機(jī),有效過(guò)程(effective procedure)與算法(algorithm)。 希爾伯特綱領(lǐng)。 1931年，奧地利25歲的數(shù)理邏輯學(xué)家哥德?tīng)?Kuri Gdel)發(fā)表了著名的不完整性理論。 具有有窮描述的過(guò)程是可數(shù)無(wú)窮多的，但函數(shù)卻是不可數(shù)無(wú)窮多的。 世界上存在著許多的問(wèn)題和函數(shù)，是無(wú)法用具有有窮描述的過(guò)程完成計(jì)算的是不可計(jì)算的(incomputable) 。,第9章 圖靈機(jī),主要內(nèi)容

5、TM作為一個(gè)計(jì)算模型，它的基本定義，即時(shí)描述，TM接受的語(yǔ)言；TM的構(gòu)造技術(shù)；TM的變形；Church-Turing論題；通用TM?？捎?jì)算語(yǔ)言、不可判定性、P-NP問(wèn)題)。 重點(diǎn) TM的定義、TM的構(gòu)造。 難點(diǎn) TM的構(gòu)造。,9.1 基本概念,圖靈提出TM具有以下兩個(gè)性質(zhì) 具有有窮描述。 過(guò)程必須是由離散的、可以機(jī)械執(zhí)行的步驟組成。 基本模型包括 一個(gè)有窮控制器。 一條含有無(wú)窮多個(gè)帶方格的輸入帶。 一個(gè)讀頭。,9.1 基本概念,一個(gè)移動(dòng)將完成以下三個(gè)動(dòng)作： 改變有窮控制器的狀態(tài)； 在當(dāng)前所讀符號(hào)所在的帶方格中印刷一個(gè)符號(hào)； 將讀頭向右或者向左移一格。,直觀物理模型,9.1.1 基本TM,圖靈機(jī)

6、(Turing machine)/基本的圖靈機(jī) TM M=(Q, , , ,q0 , B , F) ， Q為狀態(tài)的有窮集合，qQ，q為M的一個(gè)狀態(tài)； q0Q，是M的開(kāi)始狀態(tài)，對(duì)于一個(gè)給定的輸入串，M從狀態(tài)q0啟動(dòng)，讀頭正注視著輸入帶最左端的符號(hào)；,9.1.1 基本TM,FQ，是M的終止?fàn)顟B(tài)集，qF，q為M的一個(gè)終止?fàn)顟B(tài)。與FA和PDA不同，一般地，一旦M進(jìn)入終止?fàn)顟B(tài)，它就停止運(yùn)行。 為帶符號(hào)表(tape symbol)，X，X為M的一個(gè)帶符號(hào)，表示在M的運(yùn)行過(guò)程中，X可以在某一時(shí)刻出現(xiàn)在輸入帶上；,9.1.1 基本TM,B，被稱(chēng)為空白符(blank symbol)，含有空白符的帶方格被認(rèn)為是空

7、的； -B為輸入字母表，a，a為M的一個(gè)輸入符號(hào)。除了空白符號(hào)B之外，只有中的符號(hào)才能在M啟動(dòng)時(shí)出現(xiàn)在輸入帶上；,9.1.1 基本TM,：QQR, L，為M的移動(dòng)函數(shù)(transaction function)。 (q , X)=(p , Y, R)表示M在狀態(tài)q讀入符號(hào)X，將狀態(tài)改為p，并在這個(gè)X所在的帶方格中印刷符號(hào)Y，然后將讀頭向右移一格； (q , X)=(p , Y , L)表示M在狀態(tài)q讀入符號(hào)X，將狀態(tài)改為p，并在這個(gè)X所在的帶方格中印刷符號(hào)Y，然后將讀頭向左移一格。,9.1.1 基本TM,例 9-1 設(shè)M1=(q0, q1, q2,0, 1,0, 1, B,q0 , B ,q2

8、)，其中的定義如下，對(duì)于此定義，也可以用表9-1表示。 (q0, 0)= (q0, 0, R) (q0, 1)= (q1, 1, R) (q1, 0)= (q1, 0, R) (q1, B)= (q2, B, R),9.1.1 基本TM,9.1.1 基本TM,即時(shí)描述(instantaneous description, ID) 12*，qQ，1q2稱(chēng)為M的即時(shí)描述 q為M的當(dāng)前狀態(tài)。 12為M的輸入帶最左端到最右的非空白符號(hào)組成的符號(hào)串或者是M的輸入帶最左端到M的讀頭注視的帶方格中的符號(hào)組成的符號(hào)串 M正注視著2的最左符號(hào)。,9.1.1 基本TM,設(shè)X1X2Xi-1qXiXi+1Xn是M的一

9、個(gè)ID 如果(q, Xi)=(p, Y, R)，則，M的下一個(gè)ID為X1X2Xi-1YpXi+1Xn 記作 X1X2Xi-1qXiXi+1XnM X1X2Xi-1YpXi+1Xn 表示M在ID X1X2Xi-1qXiXi+1Xn下，經(jīng)過(guò)一次移動(dòng)，將ID變成X1X2Xi-1YpXi+1Xn 。,9.1.1 基本TM,如果(q, Xi)=(p, Y, L)則， 當(dāng)i1時(shí)，M的下一個(gè)ID為 X1X2pXi-1YXi+1Xn 記作 X1X2Xi-1qXiXi+1XnM X1X2pXi-1YXi+1Xn 表示M在ID X1X2Xi-1qXiXi+1Xn下，經(jīng)過(guò)一次移動(dòng)，將ID變成X1X2pXi-1YXi

10、+1Xn；,9.1.1 基本TM,M是*Q*Q*上的一個(gè)二元關(guān)系 Mn表示M的n次冪：Mn =(M)n M+表示M的正閉包：M+ =(M)+ M*表示M的克林閉包：M* =(M)* 在意義明確時(shí)，分別用、n 、+、*表示M 、Mn、M+、M*。,9.1.1 基本TM,例 9-2 例 9-1所給的M1在處理輸入串的過(guò)程中經(jīng)歷的ID變換序列。 （1）處理輸入串000100的過(guò)程中經(jīng)歷的ID的變換序列如下： q0000100M 0q000100M 00q00100 M 000q0100M 0001q100M 00010q10 M 000100 q1M 000100Bq2,9.1.1 基本TM,（2）

11、處理輸入串0001的過(guò)程中經(jīng)歷的ID變換序列如下： q00001M 0q0001M 00q001 M 000q01M 0001q1M 0001Bq2 （3）處理輸入串000101的過(guò)程中經(jīng)歷的ID變換序列如下： q0000101M 0q000101M 00q00101 M 000q0101M 0001q101M 00010q11,9.1.1 基本TM,（4）處理輸入串1的過(guò)程中經(jīng)歷的ID變換序列如下： q01M 1q1M 1Bq2 （5）處理輸入串00000的過(guò)程中經(jīng)歷的ID變換序列如下： q000000M 0q00000M 00q0000 M 000q000M 0000 q00M 00000

12、q0B,9.1.1 基本TM,TM接受的語(yǔ)言 L(M)=x | x* & q0 xM* 1 q2 & qF &1、2* TM接受的語(yǔ)言叫做遞歸可枚舉語(yǔ)言(recursively enumerable language，r.e.)。 如果存在TM M=(Q, , , ,q0 , B , F)，L=L(M)，并且對(duì)每一個(gè)輸入串x，M都停機(jī)，則稱(chēng)L為遞歸語(yǔ)言(recursively language)。,9.1.1 基本TM,例 9-3 設(shè)有M2=(q0, q1, q2, q3,0, 1,0, 1, B,q0 , B ,q3)，其中的定義如下： (q0, 0)= (q0, 0, R) (q0, 1)

13、= (q1, 1, R) (q1, 0)= (q1, 0, R) (q1, 1)= (q2, 1, R) (q2, 0)= (q2, 0, R) (q2, 1)= (q3, 1, R),9.1.1 基本TM,9.1.1 基本TM,為了弄清楚M2接受的語(yǔ)言，需要分析它的工作過(guò)程。 （1）處理輸入串00010101的過(guò)程中經(jīng)歷的ID變換序列如下： q000010101 0q00010101 00q0010101 000q010101 0001q10101 00010q1101 000101 q201000101 0 q21 00010101q3,9.1.1 基本TM,M2在q0狀態(tài)下，遇到0時(shí)狀態(tài)

14、仍然保持為q0，同時(shí)將讀頭向右移動(dòng)一格而指向下一個(gè)符號(hào)； 在q1狀態(tài)下遇到第一個(gè)1時(shí)狀態(tài)改為q1，并繼續(xù)右移讀頭，以尋找下一個(gè)1；在遇到第二個(gè)1時(shí)，動(dòng)作類(lèi)似，只是將狀態(tài)改為q2；當(dāng)遇到第三個(gè)1時(shí)，進(jìn)入終止?fàn)顟B(tài)q3，此時(shí)它正好掃描完整個(gè)輸入符號(hào)串，表示符號(hào)串被M2接受。,9.1.1 基本TM,（2）處理輸入串1001100101100的過(guò)程中經(jīng)歷的ID變換序列如下： q01001100101100 1q1001100101100 10 q101100101100 100q11100101100 1001 q210010110010011q300101100 M2遇到第三個(gè)1時(shí)，進(jìn)入終止?fàn)顟B(tài)q3，

15、輸入串的后綴00101100還沒(méi)有被處理。但是，由于M2已經(jīng)進(jìn)入終止?fàn)顟B(tài)，表示符號(hào)串1001100101100被M2接受,9.1.1 基本TM,（3）處理輸入串000101000的過(guò)程中經(jīng)歷的ID變換序列如下： q0000101000 0q000101000 00q00101000 000q0101000 0001q101000 00010q11000 000101q2000 0001010 q200 00010100 q20 000101000 q2B 當(dāng)M2的ID變?yōu)?00101000q2B時(shí)，因?yàn)闊o(wú)法進(jìn)行下一個(gè)移動(dòng)而停機(jī),不接受輸入串000101000。,9.1.1 基本TM,M2接受的

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

17、情況為 XX00YY11ZZ22BB 需要給予邊界情況密切的關(guān)注。,9.1.1 基本TM,邊界情況 XXXXYYYYZZ22BB XXXXYY11ZZ22BB XX00YYYYZZ22BB XX00YY11ZZZZBB XX00YYYYZZZZBB,構(gòu)造思路,移動(dòng)函數(shù),9.1.2 TM作為非負(fù)整函數(shù)的計(jì)算模型,非負(fù)整數(shù)進(jìn)行編碼 1進(jìn)制 用符號(hào)串0n表示非負(fù)整數(shù)n。 用符號(hào)串,表示k元函數(shù)f(n1, n2, nk)的輸入。 如果f(n1, n2, nk)=m，則該TM的輸出為0m 。,9.1.2 TM作為非負(fù)整函數(shù)的計(jì)算模型,圖靈可計(jì)算的(Turing computable) 設(shè)有k元函數(shù)f(n

18、1, n2, nk)=m，TM M=(Q, , , ,q0 , B , F)接受輸入串,輸出符號(hào)串0m；當(dāng)f(n1, n2, nk)無(wú)定義時(shí)，TM M沒(méi)有恰當(dāng)?shù)妮敵鼋o出。稱(chēng)TM M計(jì)算k元函數(shù)f(n1, n2, nk)，也稱(chēng)f(n1, n2, nk)為T(mén)M M計(jì)算的函數(shù)。也稱(chēng)f是圖靈可計(jì)算的。,9.1.2 TM作為非負(fù)整函數(shù)的計(jì)算模型,完全遞歸函數(shù)(total recursive function) 設(shè)有k元函數(shù)f(n1, n2, nk)，如果對(duì)于任意的n1, n2, nk ，f均有定義，也就是計(jì)算f的TM總能給出確定的輸出，則稱(chēng)f為完全遞歸函數(shù)。 部分遞歸函數(shù)(partial recursi

19、ve function) TM計(jì)算的函數(shù)稱(chēng)為部分遞歸函數(shù)。,9.1.2 TM作為非負(fù)整函數(shù)的計(jì)算模型,例 9-5 構(gòu)造TM M4，對(duì)于任意非負(fù)整數(shù)n，m，M4計(jì)算m+n。 分析：M4的輸入為0n10m，輸出0n+m的符號(hào)串。n和m為0的情況需要特殊考慮。 （1）當(dāng)n為0時(shí)，只用將1變成B就完成了計(jì)算，此時(shí)無(wú)需考察m是否為0； （2）當(dāng)m為0時(shí)，需要掃描過(guò)表示n的符號(hào)0，并將1改為B。 （3）當(dāng)n和m都不為0時(shí)，我們需要將符號(hào)1改為0，并將最后一個(gè)0改為B。,構(gòu)造思路,M4,M4=(q0, q1, q2, q3, 0,1, 0,1,B, , q0, B, q1) (q0，1)=(q1，B，R)

20、(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),9.1.2 TM作為非負(fù)整函數(shù)的計(jì)算模型,例 9-6 構(gòu)造TM M5，對(duì)于任意非負(fù)整數(shù)n，m，M5計(jì)算如下函數(shù)：,構(gòu)造思路,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) (q1, 1 )=(q1, 1, R) (q1, X )=(q2,

21、 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),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)。,9.1.3 TM的構(gòu)造,1. 狀態(tài)的有窮存儲(chǔ)功能的利用 例 9-7 構(gòu)造TM M6，使得L(M6)

22、=x | x0,1*& x中至多含3個(gè)1。 分析：M6只用記錄已經(jīng)讀到的1的個(gè)數(shù)。 q0表示當(dāng)前已經(jīng)讀到0個(gè)1； q1表示當(dāng)前已經(jīng)讀到1個(gè)1； q2表示當(dāng)前已經(jīng)讀到2個(gè)1； q3表示當(dāng)前已經(jīng)讀到3個(gè)1。,1. 狀態(tài)的有窮存儲(chǔ)功能的利用,M6=(q0, q1, q2, q3, qf, 0,1, 0,1,B, , q0, B, qf),(q0, 0 )=(q0, 0, R) (q0, 1 )=(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,

23、 0, R) (q2, 1 )=(q3, 1, R) (q2, B )=(qf, B, R) (q3, 0 )=(q3, 0, R) (q3, B )=(qf, B, R),1. 狀態(tài)的有窮存儲(chǔ)功能的利用,TM是要接受且僅接受恰含3個(gè)1的0、1串的TM，對(duì)M6進(jìn)行修改，得到M7 L(M7) =x | x0,1*& x中含且僅含3個(gè)1 M7=(q0, q1, q2, q3, qf, 0, 1, 0, 1, B, , q0, B, qf),L(M7) =x | x0,1*且 x中僅含3個(gè)1,(q0, 0 )=(q0, 0, R) (q0, 1 )=(q1, 1, R) (q1, 0 )=(q1,

24、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),L(M8)=x | x0,1*& x中至少含3個(gè)1,M8=(q0, q1, q2, qf, 0, 1, 0, 1, B, , q0, B, qf) (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 )=(qf, 1, R)

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

26、)=(q01, 1, R) (q01, B )=(q1, 0, R) (q1, B )=(q, 1, R),1. 狀態(tài)的有窮存儲(chǔ)功能的利用,例9-9 構(gòu)造TM M10它的輸入字母表為0，1，要求M10在它的輸入符號(hào)串的開(kāi)始處添加子串101。 將有窮控制器中的“存儲(chǔ)器”分成兩部分 第一部分用來(lái)存放待添加的子串。 第二部分用來(lái)存儲(chǔ)因添加符號(hào)串當(dāng)前需要移動(dòng)的輸入帶上暫時(shí)無(wú)帶方格存放的子串。 一般形式為qx, y x待添加子串 y當(dāng)前需要移動(dòng)的輸入帶上暫時(shí)無(wú)帶方格存放的子串。,1.狀態(tài)的有窮存儲(chǔ)功能的利用,qx, 為開(kāi)始狀態(tài)； q, 為終止?fàn)顟B(tài)。 設(shè)a、b為輸入符號(hào) (qax, y, b) = (qx

27、, yb, a, R) 表示在沒(méi)有完成待插入子串的印刷之前，要將待插入子串的首字符印刷在TM當(dāng)前掃描的帶方格上。,1. 狀態(tài)的有窮存儲(chǔ)功能的利用,(q,a y, b) = (q, yb, a, R) 表示當(dāng)完成待插入子串的插入工作之后，必須將插入點(diǎn)之后的子串順序地向后移動(dòng)。 (q,a y, B) = (q, y, a, R) 表示讀頭當(dāng)前所指的帶方格為空白，現(xiàn)將“存儲(chǔ)器”的第二部分中的當(dāng)前首符號(hào)a印刷在此帶方格上，同時(shí)將這個(gè)符號(hào)從存儲(chǔ)器中刪除。,2. 多道(multi-track)技術(shù),例9-10 構(gòu)造M11，使L(M11)=xcy | x,y0,1+ 且 xy。 分析： 以符號(hào)c為分界線，逐

28、個(gè)地將c前的符號(hào)與c后的符號(hào)進(jìn)行比較。 當(dāng)發(fā)現(xiàn)對(duì)應(yīng)符號(hào)不同時(shí)，就進(jìn)入終止?fàn)顟B(tài)。 當(dāng)發(fā)現(xiàn)x與y的長(zhǎng)度不相同而進(jìn)入終止?fàn)顟B(tài)。 發(fā)現(xiàn)它們相同而停機(jī)。 一個(gè)道存放被檢查的符號(hào)串，另一個(gè)存放標(biāo)記符。,構(gòu)造思路,2. 多道(multi-track)技術(shù),M11=(q, q0, q1, p0, p1 , q, p, s, f, 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,

29、R) (pa, ,b)=(pa, ,b, R) (pa, B,a)=(p, ,a, L),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)=(f, B,b,R) (pa, B,B)=(p, B,B, R) (s, ,b)=(s, ,b, R) (s, B,a)=(f, B,a, R),3. 子程序(subroutine)技術(shù),將TM的設(shè)計(jì)看成是一種特殊的程序設(shè)計(jì)，將子程序的概念引進(jìn)來(lái)。 一個(gè)完成某一個(gè)給定功能的TM M從一個(gè)

30、狀態(tài)q開(kāi)始，到達(dá)某一個(gè)固定的狀態(tài)f結(jié)束。 將這兩個(gè)狀態(tài)作為另一個(gè)TM M的兩個(gè)一般的狀態(tài)。 當(dāng)M進(jìn)入狀態(tài)q時(shí)，相當(dāng)于啟動(dòng)M(調(diào)用M對(duì)應(yīng)的子程序)；當(dāng)M進(jìn)入狀態(tài)f時(shí)，相當(dāng)于返回到M的狀態(tài)f。,3. 子程序(subroutine)技術(shù),例9-11 構(gòu)造M12完成正整數(shù)的乘法運(yùn)算。 分析: 設(shè)兩個(gè)正整數(shù)分別為m和n。 輸入串為0n10m 。 輸出應(yīng)該為0n*m 。 算法思想：每次將n個(gè)0中的1個(gè)0改成B，就在輸入串的后面復(fù)寫(xiě)m個(gè)0。 在M12的運(yùn)行過(guò)程中，輸入帶的內(nèi)容為 Bh0n-h10m10m*hB,正整數(shù)的乘法運(yùn)算,（1）初始化。完成將第一個(gè)0變成B，并在最后一個(gè)0后寫(xiě)上1。我們用q0表示啟動(dòng)狀

31、態(tài)，用q1表示完成初始化后的狀態(tài)。首先，消除前n個(gè)0中的第一個(gè)0， q00n10m + Bq10n-110m1 （2）主控系統(tǒng)。從狀態(tài)q1開(kāi)始，掃描過(guò)前n個(gè)0中剩余的0和第一個(gè)1，將讀頭指向m個(gè)0的第一個(gè)，此時(shí)的狀態(tài)為q2。其ID變化為 Bhq10n-h10m10m*(h-1)B + Bh0n-h1 q20m10m*(h-1)B,正整數(shù)的乘法運(yùn)算,當(dāng)子程序完成m個(gè)0的復(fù)寫(xiě)后，回到q3。這個(gè)狀態(tài)相當(dāng)于子程序的返回（終止）狀態(tài)。然后在q3狀態(tài)下，將讀頭移回到前n個(gè)0中剩余的0中的第一個(gè)0，并將這個(gè)0改成B，進(jìn)入q1狀態(tài)，準(zhǔn)備進(jìn)行下一次循環(huán) Bh0n-h1 q30m10m*hB + Bh+1q10n

32、-h-110m10m*hB,正整數(shù)的乘法運(yùn)算,當(dāng)完成m*n個(gè)0的復(fù)寫(xiě)之后，清除輸入帶上除了這m*n個(gè)0以外的其他非空白符號(hào)。q4為終止?fàn)顟B(tài) Bnq110m10m*nB + Bn+1+m+1 q4 0m*nB （3）子程序。完成將m個(gè)0復(fù)寫(xiě)到后面的任務(wù)。從q2啟動(dòng)，到q3結(jié)束，返回到主控程序。 Bh+10n-h-11 q20m10m*hB + Bh+10n-h-11 q30m10m*h+1B,9.2 TM的變形,從不同的方面對(duì)TM進(jìn)行擴(kuò)充。 雙向無(wú)窮帶TM。 多帶TM。 不確定的TM。 多維TM等。 它們與基本的TM等價(jià)。,9.2.1 雙向無(wú)窮帶TM,物理模型,9.2.1 雙向無(wú)窮帶TM,雙向無(wú)

33、窮帶 (Turing machine with two-way infinite tape，TM) TM M=(Q, , , ,q0 , B , F) Q, , , ,q0 , B , F的意義同定義9-1。 的即時(shí)描述ID同定義-2。 允許M的讀頭處在輸入串的最左端時(shí)，仍然可以向左移動(dòng)。,9.2.1 雙向無(wú)窮帶TM,M的當(dāng)前ID X1X2Xi-1qXiXi+1Xn 如果(q, Xi)=(p, Y, R) 當(dāng)i1并且YB時(shí)，M的下一個(gè)ID為 X1X2Xi-1YpXi+1Xn 記作 X1X2Xi-1qXiXi+1XnM X1X2Xi-1YpXi+1Xn 表示M在ID X1X2Xi-1qXiXi+

34、1Xn下，經(jīng)過(guò)一次移動(dòng)，將ID變成X1X2Xi-1YpXi+1Xn 。,9.2.1 雙向無(wú)窮帶TM,當(dāng)i=1并且Y=B時(shí)，M的下一個(gè)ID為 pX2Xn 記作 qX1X2XnM pX2Xn 這就是說(shuō)，和基本TM在讀頭右邊全部是B時(shí)，這些B不在ID中出現(xiàn)一樣，當(dāng)雙向無(wú)窮帶TM的讀頭左邊全部是B時(shí)，這些B也不在該TM的ID中出現(xiàn)。,9.2.1 雙向無(wú)窮帶TM,如果(q, Xi)=(p, Y, L) 當(dāng)i1時(shí)，M的下一個(gè)ID為 X1X2pXi-1YXi+1Xn 記作 X1X2Xi-1qXiXi+1XnM X1X2pXi-1YXi+1Xn 表示M在ID X1X2Xi-1qXiXi+1n下，經(jīng)過(guò)一次移動(dòng)，

35、將ID變成X1X2pXi-1YXi+1Xn 。,9.2.1 雙向無(wú)窮帶TM,當(dāng)i=1時(shí)，M的下一個(gè)ID為 pBYX2Xn 記作 qX1X2XnM pBYX2Xn 表示M在ID qX1X2Xn下，經(jīng)過(guò)一次移動(dòng)，將ID變成pBYX2Xn。,9.2.1 雙向無(wú)窮帶TM,定理9-1 對(duì)于任意一個(gè)雙向無(wú)窮帶TMM，存在一個(gè)等價(jià)的基本TMM。 證明要點(diǎn)： 雙向無(wú)窮存儲(chǔ)的模擬：用一個(gè)具有2個(gè)道的基本TM來(lái)模擬：一個(gè)道存放M開(kāi)始啟動(dòng)時(shí)讀頭所注視的帶方格及其右邊的所有帶方格中存放的內(nèi)容；另一個(gè)道按照相反的順序存放開(kāi)始啟動(dòng)時(shí)讀頭所注視的帶方格左邊的所有帶方格中存放的內(nèi)容。 雙向移動(dòng)的模擬：在第1道上，移動(dòng)的方向與

36、原來(lái)的移動(dòng)方向一致，在第2道上，移動(dòng)的方向與原來(lái)的移動(dòng)方向相反。,用單向無(wú)窮帶模擬雙向無(wú)窮帶,9.2.2 多帶TM,多帶TM(multi-tape turing machine) 允許TM有多個(gè)雙向無(wú)窮帶，每個(gè)帶上有一個(gè)相互獨(dú)立的讀頭。 k帶TM在一次移動(dòng)中完成如下三個(gè)動(dòng)作 改變當(dāng)前狀態(tài)； 各個(gè)讀頭在自己所注視的帶方格上印刷一個(gè)希望的符號(hào)。 各個(gè)讀頭向各自希望的方向移動(dòng)一個(gè)帶方格。,9.2.2 多帶TM,9.2.2 多帶TM,定理 9-2 多帶TM與基本的TM等價(jià)。 證明要點(diǎn)： 對(duì)一個(gè)k帶TM，用一條具有2k道的雙向無(wú)窮帶TMM，實(shí)現(xiàn)對(duì)這個(gè)k帶TMM的模擬。 對(duì)應(yīng)M的每一條帶，M用兩個(gè)道來(lái)實(shí)現(xiàn)

37、模擬。其中一條道用來(lái)存放對(duì)應(yīng)的帶的內(nèi)容，另一條道專(zhuān)門(mén)用來(lái)標(biāo)記對(duì)應(yīng)帶上的讀頭所在的位置。,9.2.3 不確定的TM,不確定TM與基本TM的區(qū)別是對(duì)于任意的(q，X)Q， (q，X)=(q1，Y1，D1)，(q2，Y2，D2)，(qk，Yk，Dk) Dj為讀頭的移動(dòng)方向。即DjR，L。 表示M在狀態(tài)q，讀到X時(shí)，可以有選擇地進(jìn)入狀態(tài)qj，印刷字符Yj，按Dj移動(dòng)讀頭 L(M)=w | w*且ID1*IDn，且IDn含M的終止?fàn)顟B(tài)。,9.2.3 不確定的TM,定理 9-3 不確定的TM與基本的TM等價(jià) 證明要點(diǎn)： 讓等價(jià)的基本TMM 具有3條帶。 第1條帶用來(lái)存放輸入。 第2條帶上系統(tǒng)地生成M的各種

38、可能的移動(dòng)序列 M在第3條帶上按照第2條帶上給出的移動(dòng)系列處理輸入串，如果成功，則接受之，如果不成功，則在第2條帶上生成下一個(gè)可能的移動(dòng)系列，開(kāi)始新一輪的“試處理”。,9.2.4 多維TM,多維TM(multi-dimensional Turing machine) 讀頭可以沿著多個(gè)維移動(dòng)。 k維TM(k-dimensional Turing machine) TM可以沿著k維移動(dòng)。 k維TM的帶由k維陣列組成，而且在所有的2k個(gè)方向上都是無(wú)窮的，它的讀頭可以向著2k個(gè)方向中的任一個(gè)移動(dòng)。,9.2.4 多維TM,定理 9-4 多維TM與基本TM等價(jià)。 用一維的形式表示k維的內(nèi)容，就像多維數(shù)組在

39、計(jì)算機(jī)的內(nèi)存中都被按照一維的形式實(shí)現(xiàn)存儲(chǔ)一樣。 段(Segment)用來(lái)表是一維上的內(nèi)容。 用#作為段分割符。 用作該字符串的開(kāi)始標(biāo)志，$用作該字符串的結(jié)束標(biāo)志。,基本TM模擬2維TM,基本TM模擬2維TM,Ba1a2a3a4BBBBBB # Ba5Ba6a7a8a9a10BBB # Ba11BBBBa12Ba13Ba14 # a15 a16BBBBBBBB a16# BBB a17BBBBBa18B # a19a20BBBBBBBBB # BBBBBBBBBBa21$,9.2.5 其他TM,1. 多頭TM 2. 離線TM 3. 作為枚舉器的TM 4. 多棧機(jī) 5. 計(jì)數(shù)機(jī) 6. Church

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

41、是只讀帶(read-only tape)的多帶TM。 符號(hào)和$用來(lái)限定它的輸入串存放區(qū)域，在左邊，$在右邊。 不允許該帶上的讀頭移出由和$限定的區(qū)域離線的TM。 如果只允許只讀帶上的讀頭從左向右移動(dòng)，則稱(chēng)之為在線TM(on-line Turing machine)。,2. 離線TM,定理 9-6 離線TM與基本的TM等價(jià)。 證明要點(diǎn)：讓模擬M的離線TM比M多一條帶，并且用這多出來(lái)的帶復(fù)制M的輸入串。然后將這條帶看作是M的輸入帶，模擬M進(jìn)行相應(yīng)的處理。,3. 作為枚舉器的TM,作為枚舉器的TM(Turing machine as enumerator) 多帶TM，其中有一條帶專(zhuān)門(mén)作為輸出帶，用來(lái)

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

43、-stack machines)是一個(gè)擁有一條只讀輸入帶和多條存儲(chǔ)帶的不確定TM。 多棧機(jī)的只讀帶上的讀頭不能左移。 存儲(chǔ)帶上的讀頭可以向左和向右移動(dòng)。 右移時(shí)，一般都在當(dāng)前注視的帶方格上印刷一個(gè)非空白字符 左移時(shí)，必須在當(dāng)前注視的帶方格中印刷空白字符B。 一個(gè)確定的雙棧機(jī)(double stack machines)是一個(gè)確定的TM，它具有一條只讀的輸入帶和兩條存儲(chǔ)帶。存儲(chǔ)帶上的讀頭左移時(shí)，只能印刷空白符號(hào)B 。,4. 多棧機(jī),下推自動(dòng)機(jī)是一種非確定的多帶TM。它有一條只讀的輸入帶，一條存儲(chǔ)帶。 定理 9-9 一個(gè)任意的單帶TM可以被一個(gè)確定的雙棧機(jī)模擬。,5. 計(jì)數(shù)機(jī),計(jì)數(shù)機(jī)(counte

44、r machine) 有一條只讀輸入帶和若干個(gè)用于計(jì)數(shù)的單向無(wú)窮帶的離線TM。 擁有n個(gè)用于計(jì)數(shù)帶的計(jì)數(shù)機(jī)被稱(chēng)為n計(jì)數(shù)機(jī)。 用于計(jì)數(shù)的帶上僅有兩種字符，一個(gè)為相當(dāng)于是作為棧底符號(hào)的Z，該字符也可以看作是計(jì)數(shù)帶的首符號(hào)，它僅出現(xiàn)在計(jì)數(shù)帶的最左端；另一個(gè)就是空白符B。這個(gè)帶上所記的數(shù)就是從Z開(kāi)始到讀頭當(dāng)前位置所含的B的個(gè)數(shù)。 定理 9-10 TM可以被一個(gè)雙計(jì)數(shù)機(jī)模擬。,6.丘奇-圖靈論題與隨機(jī)存取機(jī),對(duì)于任何可以用有效算法解決的問(wèn)題，都存在解決此問(wèn)題的TM。 隨機(jī)存取機(jī)(random access machine，RAM)含有無(wú)窮多個(gè)存儲(chǔ)單元，這些存儲(chǔ)單元被按照0、1、2、進(jìn)行編號(hào)，每個(gè)存儲(chǔ)單元

45、可以存放一個(gè)任意的整數(shù)；有窮個(gè)能夠保存任意整數(shù)的算術(shù)寄存器。這些整數(shù)可以被譯碼成通常的各類(lèi)計(jì)算機(jī)指令。 定理 9-11如果RAM的基本指令都能用TM來(lái)實(shí)現(xiàn)，那么就可以用TM實(shí)現(xiàn)RAM。,9.3 通用TM,通用TM(universal Turing machine) 實(shí)現(xiàn)對(duì)所有TM的模擬。 編碼系統(tǒng) 它可以在實(shí)現(xiàn)對(duì)TM的表示的同時(shí)，實(shí)現(xiàn)對(duì)該TM處理的句子的表示。 用0和1對(duì)這些除空白符以外的其他的帶符號(hào)進(jìn)行編碼。同時(shí)也可以用0和1對(duì)TM的移動(dòng)函數(shù)進(jìn)行編碼。,9.3 通用TM,M=(q1, q2, , qn, 0，1, 0，1，B, ,q1 , B , q2) 用X1、X2、X3分別表示0、1、B

46、，用D1、D2分別表示R、L。 (qi, Xj)=(qk , Xl, Dm)可以用0i10j10k10l10m表示。,9.3 通用TM,M可用 111 code1 11 code2 11 11 coder 111 codet 是動(dòng)作(qi, Xj)=(qk , Xl, Dm)的形如0i10j10k10l10m的編碼。 TMM和它的輸入串w則可以表示成 111 code1 11 code2 11 11 coder 111w 按照規(guī)范順序分別對(duì)表示TM的符號(hào)行和表示輸入的符號(hào)行進(jìn)行排序。,9.3 通用TM,Ld=w | w是第j個(gè)句子，并且第j個(gè)TM不接受它不是遞歸可枚舉語(yǔ)言。 通用語(yǔ)言(universal language) Lu= | M接受w 為如下形式的串，表示TMM=(q1, q2, , qn, 0，1, 0，1，B, ,q1 , B , q2)和它的輸入串w。 111 code1 11 code2 11 11 coder 111w,9.3 通用TM,例 9-12 設(shè)TM 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,