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

計(jì)算引論計(jì)算模型第一頁，共二十九頁，2022年，8月28日2.4圖靈機(jī)

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

第二頁，共二十九頁，2022年，8月28日2.4圖靈機(jī)當(dāng)前內(nèi)部狀態(tài)s輸入數(shù)值i輸出動作o下一時刻的內(nèi)部狀態(tài)s'

B1前移

CA0往紙帶上寫1BC0后移

A…………第三頁，共二十九頁，2022年，8月28日2.4圖靈機(jī)建模：（1）小蟲、紙帶、方格（2）黑色或者白色的信息就是小蟲的輸入信息（3）小蟲的輸出動作就是往紙帶上前爬一個方格或者后退一個方格

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

第四頁，共二十九頁，2022年，8月28日2.4圖靈機(jī)程序1：

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

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

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

，但BI；q0

,qf

Q分別稱為初始狀態(tài)和終止?fàn)顟B(tài)；第十三頁，共二十九頁，2022年，8月28日2.4圖靈機(jī)例1：(q,a)=(p,(b,L))

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

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

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

第十四頁，共二十九頁，2022年，8月28日2.4圖靈機(jī)例3：(q,a)=(q,(B,L))

說明：當(dāng)前狀態(tài)為q，讀寫頭讀取a，經(jīng)過動作后，圖靈機(jī)狀態(tài)不改變，仍為q，線性帶上a被清空為null，同時讀寫頭向左移動。第十五頁，共二十九頁，2022年，8月28日2.4圖靈機(jī)

格局(xqy)讀頭左邊信息串用x表示，右邊用y表示。初始格局：q0；終止格局：xqfy格局轉(zhuǎn)換：D1├D2設(shè)D1=xqy，y的第一個符號是a，(q,a)=(p,(b,A))；D2=x’py’第十六頁，共二十九頁，2022年，8月28日2.4圖靈機(jī)設(shè)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àn)閥中的第一個a被改寫為b,(q,a)=(p,(b,A)))第十七頁，共二十九頁，2022年，8月28日

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

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

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

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

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

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

2.4圖靈機(jī)第二十六頁，共二十九頁，2022年，8月28日

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

q00011┣Xq1011┣X0q111┣Xq20Y1┣q2X0Y1┣Xq00Y1┣XXq1Y1┣XXYq11┣XXq2YY┣Xq2XYY┣XXq0YY┣XXYq3Y┣XXYYq3B┣XXYYBq4B第二十七頁，共二十九頁，2022年，8月28日2.4圖靈機(jī)例：輸入0010

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