基本圖靈機(jī)及圖靈機(jī)的構(gòu)造技術(shù)分

1、基本圖靈機(jī)及圖靈機(jī)的構(gòu)造技術(shù)分第1頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二2School of Computer Science & Technology, BUPT主要內(nèi)容TM的基本定義TM的格局TM接受的語(yǔ)言TM的構(gòu)造技術(shù)TM的變形；重點(diǎn): TM的定義、TM的構(gòu)造。 難點(diǎn): TM的構(gòu)造。第2頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二3School of Computer Science & Technology, BUPTFinitecontrolX1BB.X2XnXi帶（tape）單元格（cell）帶符（tape symbol） 讀寫(xiě)頭在每一時(shí)刻掃描帶上

2、的一個(gè)單元 帶有一個(gè)最左單元，向右則是無(wú)限的。 帶的每個(gè)單元可容納一個(gè)帶符號(hào)開(kāi)始時(shí)，最左邊n個(gè)單元裝著輸入（n0，n為有限數(shù)），它是一個(gè)字符串，符號(hào)都選自“帶符號(hào)”的一個(gè)子集，即所謂的“輸入符號(hào)集合”。余下的有窮個(gè)單元都存放空白符，它是一個(gè)特殊的帶符號(hào)，但不是輸入符號(hào)。圖靈機(jī)的基本模型第3頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二4School of Computer Science & Technology, BUPT在一個(gè)圖靈機(jī)的動(dòng)作中，圖靈機(jī)根據(jù)帶頭（讀寫(xiě)頭）所掃描的符號(hào)和有限控制器的狀態(tài)可能作改變狀態(tài)在被掃描的帶單元上重新寫(xiě)一個(gè)符號(hào)，以代替原來(lái)寫(xiě)在該單元上的符號(hào).將帶頭

3、向左或者右移一個(gè)單元。* 圖靈機(jī)和雙向有限自動(dòng)機(jī)的區(qū)別：圖靈機(jī)能改變它帶上的符號(hào)。 圖靈機(jī)的工作機(jī)制第4頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二5School of Computer Science & Technology, BUPT圖靈機(jī)的形式化描述 有限狀態(tài)集 有限輸入符號(hào)集 有限帶符號(hào)集 轉(zhuǎn)移函數(shù) 開(kāi)始狀態(tài) 特殊帶符:空白符 終態(tài)集合q0 Q T B T F Q轉(zhuǎn)移函數(shù) : Q Q L,R 形式定義 一個(gè)圖靈機(jī) TM (Turing machine) 是一個(gè)七元組 M = (Q, T, , , q0 , B , F ). 第5頁(yè)，共31頁(yè)，2022年，5月20日，12

4、點(diǎn)25分，星期二6School of Computer Science & Technology, BUPT函數(shù)示例： Q QL ,R (q,ai)=(p,B,L) q, p Q (q,ai)=(p,b,R) ai b 格局用w1q w2描述圖靈機(jī)的瞬間工作狀態(tài)q為M的當(dāng)前狀態(tài)， w1w2 *w1w2是當(dāng)前時(shí)刻從開(kāi)始端（因?yàn)榭蓪?xiě)）到右邊空白符號(hào)為止的內(nèi)容當(dāng)讀寫(xiě)頭已達(dá)到帶的右端，則w1w2為讀寫(xiě)頭以左的內(nèi)容。約定：w1q w2表示讀寫(xiě)頭正掃描w2的最左字符w2 則表示讀寫(xiě)頭正掃描一個(gè)空白字符。圖靈機(jī)的函數(shù)與格局第6頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二7School of C

5、omputer Science & Technology, BUPT圖靈機(jī)的格局 給定圖靈機(jī) M = (Q, T, , , q0 , B , F ) ，定義格局之間的推導(dǎo)關(guān)系M 如下：1. 設(shè) (q, Xi ) = (p, Y , L )，則有 X1X2Xi-1qXiXi+1Xn M X1X2Xi-2pXi-1YXn ， 但有如下兩個(gè)例外 ： （1）i=1時(shí)， qX1X2Xn M qYX2Xn ，和 （2）i=n及 Y=B 時(shí)， X1X2Xn-1qXn M X1X2Xn-2pXn-1 B.2. 設(shè) (q, Xi ) = (p, Y , R )，則有 X1X2Xi-1 q XiXi+1Xn M

6、X1X2Xi-1Y p Xi+1Xn ， 但有如下兩個(gè)例外 ： （1）i=n時(shí)， X1X2Xn-1q Xn M X1X2Xn-1Y p B ，和 （2）i=1及 Y=B 時(shí)， q X1X2XnM B p X2Xn-1Xn.第7頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二8School of Computer Science & Technology, BUPT圖靈機(jī)接受的語(yǔ)言L(M) = T*且q0* 1 p 2 ,pF, 12* 圖靈機(jī)接受的語(yǔ)言是輸入字母表中這樣一些字符串的集合，初始時(shí)，這些字符串放在M的帶上，M處于狀態(tài)q0，且M的帶頭處在最左單元上，這些字符串將使M進(jìn)入某個(gè)

7、終止?fàn)顟B(tài)。假定： 當(dāng)輸入被接受時(shí)，圖靈機(jī)將停止，沒(méi)有下一個(gè)動(dòng)作。第8頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二9School of Computer Science & Technology, BUPT 任給圖靈機(jī) M = (Q, T, , , q0 , B , F ) ，以及輸入字符串wT*. 試問(wèn)：對(duì)于w，M 是否停機(jī)？ 停機(jī)是指圖靈機(jī)不存在下一個(gè)移動(dòng)步（move）. 結(jié)論 圖靈機(jī)的停機(jī)問(wèn)題是不可解的（即不可判定的）. 結(jié)論 任給圖靈機(jī) M ，很容易構(gòu)造一個(gè)圖靈機(jī) M，使得L(M)= L(M )，并滿足：如果wL(M) ，則對(duì)于 w，M 接受w并一定停機(jī). 如果沒(méi)有特別指出

8、，總是假定圖靈機(jī)到達(dá)終態(tài)（接受態(tài)）后一定停機(jī). 但是 ，對(duì)不能接受的字符串，圖靈機(jī)可能永不停止.（只要M還在某個(gè)輸入上運(yùn)行，我們無(wú)法知道是因?yàn)檫\(yùn)行的時(shí)間不夠長(zhǎng)而沒(méi)有被接受，還是根本就不會(huì)停機(jī)） 圖靈機(jī)的停機(jī)問(wèn)題 第9頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二10School of Computer Science & Technology, BUPT圖靈機(jī)舉例例1：設(shè)語(yǔ)言 L=an bnn=1，設(shè)計(jì)圖靈機(jī)接受L 。思路：最初帶上為 a a a b b b B B B n個(gè)a n個(gè)b首先用x替換M最左邊的a，再右移至最左邊的b用y替換之，左移尋找最右的x，然后右移一單元到最左的a

9、，重復(fù)循環(huán)。如果（1）當(dāng)在搜尋b時(shí)，M找到了空白符B，則M停止，不接受該串。 （此時(shí)，a的個(gè)數(shù)大于b的個(gè)數(shù)）（2） 當(dāng)將b改為y后，左邊再也找不到a，此時(shí),若右邊再無(wú)b，接受；若仍有b，則b的個(gè)數(shù)大于a的個(gè)數(shù)，不接受。 第10頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二11School of Computer Science & Technology, BUPT例1 L=an bnn=1(q0 ,a)=(q1 ,x,R)(q0 ,y)=(q3 ,y,R)(q1 ,a)=(q1 ,a,R)(q1 ,y)=(q1 ,y,R)(q1 ,b)=(q2 ,y,L)(q2 ,a)=(q2 ,

10、a,L)(q2 ,y)=(q2 ,y,L)(q2 ,x)=(q0 ,x,R)(q3 ,y)=(q3 ,y,R)(q3 ,B)=(q4 ,B,R) 例：aabb的接收格局序列q0aabb xq1abb xaq1bb xq2ayb q2xaybxq0aybxxq1yb xxyq1bxxq2yyxq2xyyxxq0yyxxyq3yxxyyq3Bxxyyq4 第11頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二12School of Computer Science & Technology, BUPT對(duì)于輸入字符串001122，該圖靈機(jī)可以有如下推導(dǎo)步：q0001122MXq101122

11、MX0q11122MX0Yq2122MX0Y1q222MX0Yq31Z2*Mq3X0Y1Z2MXq00Y1Z2*MXXYYZq22MXXYYq3ZZ*MXq3XYYZZMXXq0YYZZ*MXXYYq4ZZMXXYYZq5ZMXXYYZZq5BMXXYYZZBq6B例2 L = 0n1n2n n 1.第12頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二13School of Computer Science & Technology, BUPT 轉(zhuǎn)移圖與轉(zhuǎn)移表第13頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二14School of Computer Science &

12、 Technology, BUPT 作為整數(shù)函數(shù)計(jì)算機(jī)的圖靈機(jī)預(yù)備知識(shí)：圖靈機(jī)除了作為語(yǔ)言接受器外，還可看作整數(shù)到整數(shù)的函數(shù)計(jì)算機(jī)。傳統(tǒng)方法把整數(shù)表示成一進(jìn)制整數(shù) i 0 用字符串 0i 表示如果一個(gè)函數(shù)有k個(gè)自變量，i1,i2 ,ik，那么這些整數(shù)開(kāi)始時(shí)被放在帶上，并用1把他們分隔開(kāi)。形如 0i1 1 0i2 1 0i3 1 0ik如果圖靈機(jī)停止(不論是否在一個(gè)接受狀態(tài)上)且?guī)蠟?0m，則 f(i1,i2,ik)= m f是被圖靈機(jī)計(jì)算的k元函數(shù)如果f（i1,i2,ik）對(duì)所有i1,i2,ik有定義, 那么稱f是一個(gè)全遞歸函數(shù)。全遞歸函數(shù)對(duì)應(yīng)于遞歸語(yǔ)言，因?yàn)樗偸潜荒芡Ｏ聛?lái)的圖靈機(jī)所計(jì)算。

13、所有常用的整數(shù)算術(shù)函數(shù)都是全遞歸函數(shù)。第14頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二15School of Computer Science & Technology, BUPT例3：設(shè)計(jì)圖靈機(jī)求真減法思路： 1. 用空白符B代替帶上的最左端的02右移至緊跟1后的0,將其改為13左移找到B，將B之后的0改為B4重復(fù)上述過(guò)程如果（1）右移找0時(shí)，遇到B，意味著mnBBB 0 m-(n+1) 1 111 n+1 n個(gè)將后面n+1個(gè)1變?yōu)锽，將左側(cè)最后一個(gè)B變0，形如BBB 0 0 m-(n+1) BBB n個(gè) n+1個(gè) 這時(shí)，帶上留下m-n個(gè)0，即結(jié)果為m-n 初始帶 0m 10

14、n第15頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二16School of Computer Science & Technology, BUPT求真減法（續(xù)）(2) M左移找不到0，意味著 n m，形如 BBB 1 111 00 m個(gè) m個(gè) n-m個(gè) 此時(shí), 用B替換所有剩余的1 和0第16頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二17School of Computer Science & Technology, BUPT例4：L= 0 m m=2n, n 0設(shè)計(jì)思路：對(duì)輸入串w 1. 從左到右掃描帶，隔一個(gè)消一個(gè)0；2若帶上只剩唯一一個(gè)0,接受；3若帶上不止

15、一個(gè)0,且個(gè)數(shù)為奇數(shù)，拒絕；4讓讀寫(xiě)頭返回帶的最左端；5. 轉(zhuǎn)第一步。第17頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二18School of Computer Science & Technology, BUPTStartq4q2q10 / #,RqrejectX /X,RB/B,Rq3B/B,Racceptqq5# / #,RB/B,LX /X,L0 /0,L0 / X,RX /X,RX /X,R0 / X,R0 /0,R識(shí)別 L= 0 m m=2n, n 0的圖靈機(jī)第18頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二19School of Computer Sc

16、ience & Technology, BUPT課堂練習(xí)設(shè)計(jì)一個(gè)狀態(tài)數(shù)不超過(guò)3的圖靈機(jī)，它能夠接受語(yǔ)言L=a(a+b)* ，若假定T=a,b,兩個(gè)狀態(tài)的圖靈機(jī)能否接受該語(yǔ)言？第19頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二20School of Computer Science & Technology, BUPT5.2 圖靈機(jī)的構(gòu)造技術(shù) 在設(shè)計(jì)圖靈機(jī)的過(guò)程中，寫(xiě)出函數(shù)很麻煩，為了構(gòu)造復(fù)雜的圖靈機(jī)，需探討圖靈機(jī)的若干構(gòu)造技術(shù)，并引入一些新的概念和工具。目的：設(shè)計(jì)時(shí)方便，但這些構(gòu)造技術(shù)并未增加圖靈機(jī)的功能。 第20頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二21Sc

17、hool of Computer Science & Technology, BUPT5.2.1. 利用帶存儲(chǔ)區(qū)的狀態(tài)（storage in the state）此類圖靈機(jī) M = (Q, , , , q0 , B , F ) 中，狀態(tài)中可以包含一個(gè)具有有限個(gè)取值的存儲(chǔ)單元，即狀態(tài)集合為 Q = ST = q,a | qS aT ，其中 qS 通常表示控制狀態(tài)，而 aT 通常表示數(shù)據(jù)元素.一般情況下，有限控制器內(nèi)允許存儲(chǔ)n個(gè)字符，即狀態(tài)的第2個(gè)元素可存儲(chǔ)n個(gè)字符。第21頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二22School of Computer Science & Tec

18、hnology, BUPT例：設(shè)計(jì)一個(gè)圖靈機(jī)，讀寫(xiě)頭將掃視第一個(gè)字符存入有限控制器內(nèi)，然后掃視整個(gè)帶，若找不到與第一個(gè)相同的字符，則M接受該字符串，否則不接受。構(gòu)造M=(Q,a,b,a,b,B,q0,B,F)其中Q=q0,q1a,b,B=q0,a,q0,b,q0,Bq1,aq1,bq1,B初態(tài)q0,B終態(tài)F=q1,B 函數(shù)：(q0,B,a)=( q1,a,a,R)(q0,B,b)=( q1,b,b,R) 存第一個(gè)字符(q1,a,b)=( q1,a,b,R)(q1,b,a)=( q1,b,a,R) 后面符號(hào)與第一個(gè)不等，繼續(xù)右移(q1,a,B)=( q1,B,B,L)(q1,b,B)=( q1,

19、B,B,L) 進(jìn)入終態(tài)q1,B(q1,a,a)=(q1,b,b)= 遇到相同符號(hào)，無(wú)定義 M停機(jī)，不接受第22頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二23School of Computer Science & Technology, BUPT5.2.2 多道（multiple tracks）圖靈機(jī)把圖靈機(jī)的輸入帶分成兩層或多層，這樣，原來(lái)的每一單元變成了上下兩個(gè)或多個(gè)單元。對(duì)含有n層的輸入帶來(lái)說(shuō)，讀寫(xiě)頭一次可同時(shí)讀出并改寫(xiě)n個(gè)單元的字符，這樣的圖靈機(jī)稱為n道機(jī)。 第23頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二24School of Computer Sci

20、ence & Technology, BUPT例： 多道圖靈機(jī)例：用三道機(jī)，檢查某個(gè)數(shù)n（n2）是否為素?cái)?shù)。（書(shū)p196）思路：將被檢查的數(shù)n以二進(jìn)制形式寫(xiě)在輸入帶的第一道上，數(shù)的兩端分別用￥和定界允許的輸入符號(hào)為￥,B,B,0,B,B,1,B,B,B,B分別代表1，2，3帶上的內(nèi)容。檢查方法：在第二道上寫(xiě)下一個(gè)二進(jìn)制數(shù)2把第一道上的數(shù)復(fù)制到第三道上將第三道上的數(shù)減去第二道上的數(shù)，余數(shù)留在第三道上若余數(shù)為0，被檢查的數(shù)不是素?cái)?shù)若余數(shù)不為0，將第二道數(shù)加1，將第一道數(shù)復(fù)制到第三道，重復(fù)上述1，2，3，4過(guò)程當(dāng)一，二道數(shù)相等時(shí)，該數(shù)時(shí)素?cái)?shù)。 第24頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分

21、，星期二25School of Computer Science & Technology, BUPT 5.2.3 核對(duì)符 當(dāng)用圖靈機(jī)識(shí)別語(yǔ)言時(shí)，如果語(yǔ)言中存在有重復(fù)性或可逆性等類型的句子時(shí)，為了判定某個(gè)字符串是否屬于語(yǔ)句中的句子，可以使用一個(gè)核對(duì)符，以此增加圖靈機(jī)的靈活性。 考慮用一個(gè)雙道機(jī)，在第二道上使用核對(duì)符“”，在第一道上放要被檢查的字符串,當(dāng)字符串中某個(gè)字符一旦被核對(duì)以后,可以在第二道上對(duì)應(yīng)位置寫(xiě)上核對(duì)符“”。第25頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二26School of Computer Science & Technology, BUPT例： 核對(duì)符例：設(shè)

22、計(jì)一個(gè)圖靈機(jī)M，能夠識(shí)別語(yǔ)言wtwwa,b*思路：以t為分界符，一個(gè)一個(gè)比較。解：構(gòu)造M=(Q,T, , ,q0，B,F)其中Q=qi,c i=1,2,9,c=a,b或B狀態(tài)第二元素可存儲(chǔ)一個(gè)字符。T=c，B c=a,b或t 兩道與一道不同的表示法c，Y c=a,b,t或B,Y=B或 q0=q1,B, F=q9,B空白符B在二道機(jī)下表示為B，B第26頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二27School of Computer Science & Technology, BUPT例： 核對(duì)符第27頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二28School o

23、f Computer Science & Technology, BUPT核對(duì)符例 ： abtab的分析過(guò)程q1,Babtabaq2,abtababq2,atababtq3,aab abq4,Btabaq5,Bbtabq6,Babtab aq1,Bbtababq2,btababtq3,bab abtaq3,bbabtq4,Babaq5,Bbtab abq7,Btababtq8,Bababtaq8,Bb 第28頁(yè)，共31頁(yè)，2022年，5月20日，12點(diǎn)25分，星期二29School of Computer Science & Technology, BUPT 5.2.4 移位 可以讓圖靈機(jī)具備移位的功能