基本圖靈機及圖靈機的構造技術分第一頁，共三十一頁，2022年，8月28日2SchoolofComputerScience&Technology,BUPT主要內容TM的基本定義TM的格局TM接受的語言TM的構造技術TM的變形；重點:TM的定義、TM的構造。難點:TM的構造。第二頁，共三十一頁，2022年，8月28日3SchoolofComputerScience&Technology,BUPTFinitecontrolX1BB...X2XnXi帶（tape）單元格（cell）帶符（tapesymbol）讀寫頭在每一時刻掃描帶上的一個單元帶有一個最左單元，向右則是無限的。帶的每個單元可容納一個帶符號開始時，最左邊n個單元裝著輸入（n>＝0，n為有限數），它是一個字符串，符號都選自“帶符號”的一個子集，即所謂的“輸入符號集合”。余下的有窮個單元都存放空白符，它是一個特殊的帶符號，但不是輸入符號。圖靈機的基本模型第三頁，共三十一頁，2022年，8月28日4SchoolofComputerScience&Technology,BUPT 在一個圖靈機的動作中，圖靈機根據帶頭（讀寫頭）所掃描的符號和有限控制器的狀態可能作改變狀態在被掃描的帶單元上重新寫一個符號，以代替原來寫在該單元上的符號.將帶頭向左或者右移一個單元。*圖靈機和雙向有限自動機的區別：圖靈機能改變它帶上的符號。圖靈機的工作機制第四頁，共三十一頁，2022年，8月28日5SchoolofComputerScience&Technology,BUPT圖靈機的形式化描述有限狀態集

有限輸入符號集

有限帶符號集

轉移函數

開始狀態

特殊帶符:空白符

終態集合q0Q

T

B–T

FQ轉移函數:QQ{L,R}形式定義一個圖靈機TM(Turingmachine)是一個七元組

M=(Q,T,,,q0,B

,F).

第五頁，共三十一頁，2022年，8月28日6SchoolofComputerScience&Technology,BUPTδ函數示例：Q×∑→Q×∑×{L,R}δ(q,ai)=(p,B,L)q,p∈Qδ(q,ai)=(p,b,R)ai∈∑b∈∑

格局用w1qw2描述圖靈機的瞬間工作狀態q為M的當前狀態，w1w2∈∑*w1w2是當前時刻從開始端（因為可寫）到右邊空白符號為止的內容當讀寫頭已達到帶的右端，則w1w2為讀寫頭以左的內容。約定：w1qw2表示讀寫頭正掃描w2的最左字符

w2＝則表示讀寫頭正掃描一個空白字符。圖靈機的函數與格局第六頁，共三十一頁，2022年，8月28日7SchoolofComputerScience&Technology,BUPT圖靈機的格局給定圖靈機M=(Q,T,,,q0,B

,F)，定義格局之間的推導關系├M

如下：1.設(q,Xi)

=(p,Y

,L)，則有

X1X2…Xi-1qXiXi+1…Xn

├MX1X2…Xi-2pXi-1Y…Xn

，但有如下兩個例外

：（1）i=1時，qX1X2…Xn

├MqYX2…Xn

，和（2）i=n及Y=B

時，X1X2…Xn-1qXn

├MX1X2…Xn-2pXn-1

B.2.設(q,Xi)

=(p,Y

,R)，則有

X1X2…Xi-1qXiXi+1…Xn

├MX1X2…Xi-1YpXi+1…Xn

，但有如下兩個例外

：（1）i=n時，X1X2…Xn-1qXn

├MX1X2…Xn-1YpB

，和（2）i=1及Y=B

時，qX1X2…Xn├MB

pX2…Xn-1Xn.第七頁，共三十一頁，2022年，8月28日8SchoolofComputerScience&Technology,BUPT圖靈機接受的語言L(M)={ω│ω∈T*且q0ω├*α1pα2,p∈F,α1α2∈∑*}圖靈機接受的語言是輸入字母表中這樣一些字符串的集合，初始時，這些字符串放在M的帶上，M處于狀態q0，且M的帶頭處在最左單元上，這些字符串將使M進入某個終止狀態。假定：當輸入被接受時，圖靈機將停止，沒有下一個動作。第八頁，共三十一頁，2022年，8月28日9SchoolofComputerScience&Technology,BUPT任給圖靈機M=(Q,T,,,q0,B

,F)，以及輸入字符串wT*.試問：對于w，M是否停機？停機是指圖靈機不存在下一個移動步（move）.結論圖靈機的停機問題是不可解的（即不可判定的）.結論任給圖靈機M

，很容易構造一個圖靈機M，使得L(M)=L(M)，并滿足：如果wL(M)

，則對于w，M接受w并一定停機.如果沒有特別指出，總是假定圖靈機到達終態（接受態）后一定停機.但是，對不能接受的字符串，圖靈機可能永不停止.（只要M還在某個輸入上運行，我們無法知道是因為運行的時間不夠長而沒有被接受，還是根本就不會停機）

圖靈機的停機問題

第九頁，共三十一頁，2022年，8月28日10SchoolofComputerScience&Technology,BUPT圖靈機舉例例1：設語言L={anbn│n>=1}，設計圖靈機接受L。思路：最初帶上為aa

…

abb…bBBB…… n個an個b首先用x替換M最左邊的a，再右移至最左邊的b用y替換之，左移尋找最右的x，然后右移一單元到最左的a，重復循環。如果（1）當在搜尋b時，M找到了空白符B，則M停止，不接受該串。（此時，a的個數大于b的個數）（2）當將b改為y后，左邊再也找不到a，此時,若右邊再無b，接受；若仍有b，則b的個數大于a的個數，不接受。第十頁，共三十一頁，2022年，8月28日11SchoolofComputerScience&Technology,BUPT例1L={anbn│n>=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,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├q2xayb├xq0ayb├xxq1yb├xxyq1b├xxq2yy├xq2xyy├xxq0yy├xxyq3y├xxyyq3B├xxyyq4

第十一頁，共三十一頁，2022年，8月28日12SchoolofComputerScience&Technology,BUPT對于輸入字符串001122，該圖靈機可以有如下推導步：q0001122├MXq101122├MX0q11122├MX0Yq2122├MX0Y1q222├MX0Yq31Z2├*Mq3X0Y1Z2├MXq00Y1Z2├*MXXYYZq22├MXXYYq3ZZ├*MXq3XYYZZ├MXXq0YYZZ├*MXXYYq4ZZ├MXXYYZq5Z├MXXYYZZq5B├MXXYYZZBq6B例2

L=0n1n2n

n

1.第十二頁，共三十一頁，2022年，8月28日13SchoolofComputerScience&Technology,BUPT

轉移圖與轉移表第十三頁，共三十一頁，2022年，8月28日14SchoolofComputerScience&Technology,BUPT作為整數函數計算機的圖靈機預備知識：圖靈機除了作為語言接受器外，還可看作整數到整數的函數計算機。傳統方法把整數表示成一進制

整數i0用字符串0i表示如果一個函數有k個自變量，i1,i2,…ik，那么這些整數開始時被放在帶上，并用1把他們分隔開。 形如0i110i210i3…10ik如果圖靈機停止(不論是否在一個接受狀態上)且帶上為0m，則f(i1,i2,…,ik)=mf是被圖靈機計算的k元函數如果f（i1,i2…,ik）對所有i1,i2…,ik有定義,那么稱f是一個全遞歸函數。全遞歸函數對應于遞歸語言，因為它總是被能停下來的圖靈機所計算。所有常用的整數算術函數都是全遞歸函數。第十四頁，共三十一頁，2022年，8月28日15SchoolofComputerScience&Technology,BUPT例3：設計圖靈機求真減法思路：1.用空白符B代替帶上的最左端的02．右移至緊跟1后的0,將其改為13．左移找到B，將B之后的0改為B4．重復上述過程如果（1）右移找0時，遇到B，意味著m>nBB…B0m-(n+1)111…1n+1n個將后面n+1個1變為B，將左側最后一個B變0，形如BB…B00m-(n+1)BB…Bn個n+1個

這時，帶上留下m-n個0，即結果為m-n

初始帶0m10n第十五頁，共三十一頁，2022年，8月28日16SchoolofComputerScience&Technology,BUPT求真減法（續）(2)M左移找不到0，意味著nm，形如

BB…B111…10…0m個m個n-m個

此時,用B替換所有剩余的1和0第十六頁，共三十一頁，2022年，8月28日17SchoolofComputerScience&Technology,BUPT例4：L=0mm=2n,n0設計思路：對輸入串w

1.從左到右掃描帶，隔一個消一個0；2．若帶上只剩唯一一個0,接受；3．若帶上不止一個0,且個數為奇數，拒絕；4．讓讀寫頭返回帶的最左端；5.轉第一步。第十七頁，共三十一頁，2022年，8月28日18SchoolofComputerScience&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識別

L=0mm=2n,n0的圖靈機第十八頁，共三十一頁，2022年，8月28日19SchoolofComputerScience&Technology,BUPT課堂練習設計一個狀態數不超過3的圖靈機，它能夠接受語言L=a(a+b)*，若假定T={a,b},兩個狀態的圖靈機能否接受該語言？第十九頁，共三十一頁，2022年，8月28日20SchoolofComputerScience&Technology,BUPT5.2圖靈機的構造技術在設計圖靈機的過程中，寫出δ函數很麻煩，為了構造復雜的圖靈機，需探討圖靈機的若干構造技術，并引入一些新的概念和工具。目的：設計時方便，但這些構造技術并未增加圖靈機的功能。第二十頁，共三十一頁，2022年，8月28日21SchoolofComputerScience&Technology,BUPT5.2.1.利用帶存儲區的狀態（storageinthestate）此類圖靈機M=(Q,

,,,q0,B

,F)

中，狀態中可以包含一個具有有限個取值的存儲單元，即狀態集合為

Q=ST={[q,a]|qSaT}，其中qS通常表示控制狀態，而aT通常表示數據元素.一般情況下，有限控制器內允許存儲n個字符，即狀態的第2個元素可存儲n個字符。第二十一頁，共三十一頁，2022年，8月28日22SchoolofComputerScience&Technology,BUPT例：設計一個圖靈機，讀寫頭將掃視第一個字符存入有限控制器內，然后掃視整個帶，若找不到與第一個相同的字符，則M接受該字符串，否則不接受。構造M=(Q,{a,b},{a,b,B},δ,q0,B,F)其中Q={q0,q1}×{a,b,B}={[q0,a],[q0,b],[q0,B][q1,a][q1,b][q1,B]}初態[q0,B]終態F={[q1,B]}δ函數：δ([q0,B],a)=([q1,a],a,R)δ([q0,B],b)=([q1,b],b,R)存第一個字符δ([q1,a],b)=([q1,a],b,R)δ([q1,b],a)=([q1,b],a,R)后面符號與第一個不等，繼續右移δ([q1,a],B)=([q1,B],B,L)δ([q1,b],B)=([q1,B],B,L)進入終態[q1,B]δ([q1,a],a)=Фδ([q1,b],b)=Ф遇到相同符號，δ無定義

M停機，不接受第二十二頁，共三十一頁，2022年，8月28日23SchoolofComputerScience&Technology,BUPT5.2.2多道（multipletracks）圖靈機把圖靈機的輸入帶分成兩層或多層，這樣，原來的每一單元變成了上下兩個或多個單元。對含有n層的輸入帶來說，讀寫頭一次可同時讀出并改寫n個單元的字符，這樣的圖靈機稱為n道機。

第二十三頁，共三十一頁，2022年，8月28日24SchoolofComputerScience&Technology,BUPT例：多道圖靈機例：用三道機，檢查某個數n（n>2）是否為素數。（書p196）思路：將被檢查的數n以二進制形式寫在輸入帶的第一道上，數的兩端分別用￥和Ф定界允許的輸入符號為[￥,B,B],[0,B,B],[1,B,B],[Ф,B,B][…]分別代表1，2，3帶上的內容。檢查方法：在第二道上寫下一個二進制數2把第一道上的數復制到第三道上將第三道上的數減去第二道上的數，余數留在第三道上若余數為0，被檢查的數不是素數若余數不為0，將第二道數加1，將第一道數復制到第三道，重復上述1，2，3，4過程當一，二道數相等時，該數時素數。

第二十四頁，共三十一頁，2022年，8月28日25SchoolofComputerScience&Technology,BUPT

5.2.3核對符當用圖靈機識別語言時，如果語言中存在有重復性或可逆性等類型的句子時，為了判定某個字符串是否屬于語句中的句子，可以使用一個核對符，以此增加圖靈機的靈活性。考慮用一個雙道機，在第二道上使用核對符“”，在第一道上放要被檢查的字符串,當字符串中某個字符一旦被核對以后,可以在第二道上對應位置寫上核對符“”。第二十五頁，共三十一頁，2022年，8月28日26SchoolofComputerScience&Technology,BUPT例：核對符例：設計一個圖靈機M，能夠識別語言{wtw│w∈{a,b}*}思路：以t為分界符，一個一個比較。解：構造M=(Q,T,∑,δ,q0，B,F)其中Q={[qi,c]│i=1,2,…,9,c=a,b或B}狀態第二元素可存儲一個字符。T={[c，B]}│c=a,b或t}兩道與一道不同的表示法∑＝{[c，Y]}│c=a,b,t或B,Y=B或

}q0=[q1,B],F={[q9,B]}空白符B在二道機下表示為[B，B]第二十六頁，共三十一頁，2022年，8月28日27SchoolofComputerScience&Technology,BUPT例：核對符第二十七頁，共三十一頁，2022年，8月28日28SchoolofComputerScience&Technology,BUPT核對符例：abtab的分析過程[q1,B]abtab├a[q2,a]btab├ab[q2,a]tab├abt[q3,a]ab

├ab[q4,B]tab├a[q5,B]btab├[q6,B]abtab

├a[q1,B]btab├ab[q2,b]tab├abt[q3,b]ab

├abta[q3,b]b├abt[q4,B]ab├a[q5,B]btab

├ab[q7,B]tab├abt[q8,B]ab├abta[q8,B]b…

第二十八頁，共三十一頁，2022年，8月28日29SchoolofComputerScience&Techn