計算引論 計算模型

計算引論計算模型第1頁，共29頁，2023年，2月20日，星期四2.4圖靈機

這個裝置由下面幾個部分組成：一個無限長的紙帶，一個讀寫頭（中間那個大盒子），內部狀態(tài)（盒子上的方塊，比如A,B,E,H），另外，還有一個程序對這個盒子進行控制。這個裝置就是根據(jù)程序的命令以及它的內部狀態(tài)進行磁帶的讀寫、移動。

第2頁，共29頁，2023年，2月20日，星期四2.4圖靈機當前內部狀態(tài)s輸入數(shù)值i輸出動作o下一時刻的內部狀態(tài)s'

B1前移

CA0往紙帶上寫1BC0后移

A…………第3頁，共29頁，2023年，2月20日，星期四2.4圖靈機建模：（1）小蟲、紙帶、方格（2）黑色或者白色的信息就是小蟲的輸入信息（3）小蟲的輸出動作就是往紙帶上前爬一個方格或者后退一個方格

（4）行動的規(guī)則

第4頁，共29頁，2023年，2月20日，星期四2.4圖靈機程序1：

第5頁，共29頁，2023年，2月20日，星期四2.4圖靈機程序2：123第6頁，共29頁，2023年，2月20日，星期四2.4圖靈機程序24567第7頁，共29頁，2023年，2月20日，星期四2.4圖靈機程序312第8頁，共29頁，2023年，2月20日，星期四2.4圖靈機345第9頁，共29頁，2023年，2月20日，星期四2.4圖靈機678第10頁，共29頁，2023年，2月20日，星期四2.4圖靈機小蟲模型是對圖靈機一個模擬，可以把小蟲的輸入集合、輸出行動集合、內部狀態(tài)集合進行擴大。接下來對圖靈機模型進行形式說明。第11頁，共29頁，2023年，2月20日，星期四2.4圖靈機組成：1、線性帶（讀寫介質）2、基本符號表（表示信息）3、信息處理狀態(tài)4、信息處理動作（靜止，左、右移）5、信息處理方法（規(guī)則，即程序）第12頁，共29頁，2023年，2月20日，星期四2.4圖靈機圖靈機模型M如下表示：

M＝(Q,,I,,B,q0,qf)

其中：Q為狀態(tài)的有限集合；為線性帶符號集；I為輸入符號集，有I為的子集；為Q×Q×(×{L,R})。為映射，×為笛卡爾積?？煞Q為動作函數(shù)(Q,)，其中，L、R分別表示讀寫頭左移、右移；B為null(空白)，長度為0。有B

，但BI；q0

,qf

Q分別稱為初始狀態(tài)和終止狀態(tài)；第13頁，共29頁，2023年，2月20日，星期四2.4圖靈機例1：(q,a)=(p,(b,L))

說明：當前狀態(tài)為q，讀寫頭讀取a，經(jīng)過動作后，圖靈機狀態(tài)改為p，線性帶上a改變?yōu)閎，同時讀寫頭左移一格。

例2：(q,a)=(p,(a,R))

說明：當前狀態(tài)為q，讀寫頭讀取a，經(jīng)過δ動作后，圖靈機狀態(tài)改為p，線性帶上a不改變，同時讀寫頭右移一格。

第14頁，共29頁，2023年，2月20日，星期四2.4圖靈機例3：(q,a)=(q,(B,L))

說明：當前狀態(tài)為q，讀寫頭讀取a，經(jīng)過動作后，圖靈機狀態(tài)不改變，仍為q，線性帶上a被清空為null，同時讀寫頭向左移動。第15頁，共29頁，2023年，2月20日，星期四2.4圖靈機

格局(xqy)讀頭左邊信息串用x表示，右邊用y表示。初始格局：q0；終止格局：xqfy格局轉換：D1├D2設D1=xqy，y的第一個符號是a，(q,a)=(p,(b,A))；D2=x’py’第16頁，共29頁，2023年，2月20日，星期四2.4圖靈機設x=x1?c，y=a?y1，D1=xqy(1)若A=L,則D2=x’py’（左移）其中x’=x去掉最后一個符號所得的串x’=x1，y’=x最后一個符號+b+(y減去第一個符號)，即y’=c?b?y1(因為y中的第一個a被改寫為b,(q,a)=(p,(b,A)))第17頁，共29頁，2023年，2月20日，星期四

2.4圖靈機(2)若A=R,則D2=x’py’，其中x’=x?b，y’=y1

滿足上述兩種情況的D1和D2稱為具有格局轉換關系，記為D1┣D2。第18頁，共29頁，2023年，2月20日，星期四2.4圖靈機如果用X1X2…Xi-1qXiXi+1…Xn來表示格局，其中1、q是圖靈機的狀態(tài)；2、讀寫頭正在掃描左起第i個符號；3、X1X2…Xn是帶的最左邊與最右邊非空格之間的部分。第19頁，共29頁，2023年，2月20日，星期四2.4圖靈機那么假設(q,Xi)=(p,(Y,L))，即下一步移動是向左的，則：X1X2…Xi-1qXiXi+1…Xn┣X1X2…Xi-2pXi-1YXi+1…Xn第20頁，共29頁，2023年，2月20日，星期四

2.4圖靈機1、如果i=1，則讀寫頭移動到X1左邊的空格qX1X2…Xn┣pBYX2…Xn2、如果i=n且Y=B，則在Xn上寫下的符號B加入后面空格的無窮序列，并且不出現(xiàn)在下一個格局中X1X2…Xn-1qXn┣X1X2…Xn-2pXn-1第21頁，共29頁，2023年，2月20日，星期四

2.4圖靈機轉換關系的閉包┣*表示多步轉換，即如D┣*E，則存在D1…Dk，使得D┣D1，D1┣D2，…，Dk┣E定義：q0┣*xqfy稱為一個以為輸入，x?y為輸出的計算，即一個計算是格局轉換序列，是從初始格局到終止格局按照動作函數(shù)規(guī)定的規(guī)則進行的一系列轉換。第22頁，共29頁，2023年，2月20日，星期四2.4圖靈機例：設計一臺接受0與1出現(xiàn)次數(shù)相同且0先出現(xiàn)的串的Turing機。

基本思路是：讀頭將第一個0改為x，右移，把找到的第一個1改為y，然后退回去直到遇到第一個x，再右移把遇到的第一個0改為x，右移，把找到的第一個1改為y，如此反復直到讀頭指向B（空白）為止。

第23頁，共29頁，2023年，2月20日，星期四2.4圖靈機具體步驟:1)從輸入左端開始，進入一個循環(huán)，在這個循環(huán)中把一個0改成X;2)向右移動越過看到的任何0和Y，直到到達1,把這個1改成Y;3)向左移動越過Y和0，直到發(fā)現(xiàn)一個X。在這個時刻，尋找右邊緊挨著的0，如果找到0，就把這個0改成X;4)重復上述過程，把一個匹配的1改成Y。第24頁，共29頁，2023年，2月20日，星期四2.4圖靈機如果非空格輸入不是0n1n的形式，則圖靈機將無法進行下一步移動，并且將死機而不接受。則圖靈機定義如下:M=({q0,q1,q2,q3,q4},{0,1,B,x,y},{0,1},,B,q0,q4)第25頁，共29頁，2023年，2月20日，星期四

2.4圖靈機第26頁，共29頁，2023年，2月20日，星期四

2.4圖靈機例：輸入0011

q00011┣Xq1011┣X0q111┣Xq20Y1┣q2X0Y1┣Xq00Y1┣XXq1Y1┣XXYq11┣XXq2YY┣Xq2XYY┣XXq0YY┣XXYq3Y┣XXYYq3B┣XXYYBq4B第27頁，共29頁，2023年，2月20日，星期四2.4圖靈機例：輸入0010

q00010┣Xq1010┣X0q110┣Xq20Y0┣q2X0Y0┣Xq00Y0┣XXq1Y0┣XXYq10