計(jì)算引論 計(jì)算模型

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

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

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

B1前移

CA0往紙帶上寫1BC0后移

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

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

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

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

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

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

，但BI；q0

,qf

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4圖靈機(jī)例：輸入0011

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

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