第二講圖靈機(jī)模型

第二講圖靈機(jī)模型1第1頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月主要內(nèi)容、重難點(diǎn)主要內(nèi)容圖靈機(jī)作為一個(gè)計(jì)算模型，它的基本定義，即時(shí)描述，圖靈機(jī)接受的語(yǔ)言；圖靈機(jī)的構(gòu)造技術(shù)；圖靈機(jī)的變形；Church-Turing論題；通用圖靈機(jī)。可計(jì)算語(yǔ)言、不可判定性、P-NP問(wèn)題)。重點(diǎn)圖靈機(jī)的定義、圖靈機(jī)的構(gòu)造。

難點(diǎn)圖靈機(jī)的構(gòu)造。

2第2頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1基本概念

圖靈提出圖靈機(jī)具有以下兩個(gè)性質(zhì)具有有窮描述。過(guò)程必須是由離散的、可以機(jī)械執(zhí)行的步驟組成?；灸Ｐ桶ㄒ粋€(gè)有窮控制器。一條含有無(wú)窮多個(gè)帶方格的輸入帶。一個(gè)讀頭。一個(gè)移動(dòng)將完成以下三個(gè)動(dòng)作改變有窮控制器的狀態(tài)；在當(dāng)前所讀符號(hào)所在的帶方格中印刷一個(gè)符號(hào)；將讀頭向右或者向左移一格。3第3頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月直觀物理模型4第4頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)圖靈機(jī)（Turingmachine）/基本的圖靈機(jī)M=(Q,∑,Γ,δ,q0,B,F)，Q為狀態(tài)的有窮集合，

q∈Q，q為M的一個(gè)狀態(tài)；q0∈Q，是M的開(kāi)始狀態(tài)，對(duì)于一個(gè)給定的輸入串，M從狀態(tài)q0啟動(dòng)，讀頭正注視著輸入帶最左端的符號(hào)；5第5頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)F

Q，是M的終止?fàn)顟B(tài)集，

q∈F，q為M的一個(gè)終止?fàn)顟B(tài)。與FA和PDA不同，一般地，一旦M進(jìn)入終止?fàn)顟B(tài)，它就停止運(yùn)行；Γ為帶符號(hào)表（tapesymbol），

X∈Γ，X為M的一個(gè)帶符號(hào)，表示在M的運(yùn)行過(guò)程中，X可以在某一時(shí)刻出現(xiàn)在輸入帶上；6第6頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)B∈Γ，被稱(chēng)為空白符（blanksymbol），含有空白符的帶方格被認(rèn)為是空的；∑

Γ-{B}為輸入字母表，

a∈∑，a為M的一個(gè)輸入符號(hào)。除了空白符號(hào)B之外，只有∑中的符號(hào)才能在M啟動(dòng)時(shí)出現(xiàn)在輸入帶上；

7第7頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)δ：Q×Γ

Q×?！羬R,L}，為M的移動(dòng)函數(shù)（transactionfunction）。δ(q,X)=(p,Y,R)表示M在狀態(tài)q讀入符號(hào)X，將狀態(tài)改為p，并在這個(gè)X所在的帶方格中印刷符號(hào)Y，然后將讀頭向右移一格；δ(q,X)=(p,Y,L)表示M在狀態(tài)q讀入符號(hào)X，將狀態(tài)改為p，并在這個(gè)X所在的帶方格中印刷符號(hào)Y，然后將讀頭向左移一格。

8第8頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月例子2-1說(shuō)明例2-1設(shè)M1=({q0,q1,q2},{0,1},{0,1,B},δ,q0,B,{q2})，其中δ的定義如下，對(duì)于此定義，也可以用表2-1表示。

δ(q0,0)=(q0,0,R) δ(q0,1)=(q1,1,R) δ(q1,0)=(q1,0,R) δ(q1,B)=(q2,B,R)9第9頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月例子2-1說(shuō)明

01Bq0(q0,0,R)(q1,1,R)

q1(q1,0,R)

(q2,B,R)q2

10第10頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)即時(shí)描述(instantaneousdescription,ID)

α1α2∈Γ*，q∈Q，α1qα2稱(chēng)為M的即時(shí)描述q為M的當(dāng)前狀態(tài)。α1α2為M的輸入帶最左端到最右的非空白符號(hào)組成的符號(hào)串或者是M的輸入帶最左端到M的讀頭注視的帶方格中的符號(hào)組成的符號(hào)串M正注視著α2的最左符號(hào)。11第11頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)設(shè)X1X2…Xi-1qXiXi+1…Xn是M的一個(gè)ID

如果δ(q,Xi)=(p,Y,R)，則，M的下一個(gè)ID為X1X2…Xi-1YpXi+1…Xn

記作X1X2…Xi-1qXiXi+1…Xn├MX1X2…Xi-1YpXi+1…Xn

表示M在IDX1X2…Xi-1qXiXi+1…Xn下，經(jīng)過(guò)一次移動(dòng)，將ID變成X1X2…Xi-1YpXi+1…Xn

。12第12頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)如果δ(q,Xi)=(p,Y,L)則，當(dāng)i≠1時(shí)，M的下一個(gè)ID為

X1X2…pXi-1YXi+1…Xn記作X1X2…Xi-1qXiXi+1…Xn├MX1X2…pXi-1YXi+1…Xn表示M在IDX1X2…Xi-1qXiXi+1…Xn下，經(jīng)過(guò)一次移動(dòng)，將ID變成X1X2…pXi-1YXi+1…Xn；

13第13頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)├M是Γ*QΓ*×Γ*QΓ*上的一個(gè)二元關(guān)系

├Mn表示├M的n次冪：├Mn=(├M)n├M+表示├M的正閉包：├M+=(├M)+├M*表示├M的克林閉包：├M*=(├M)*在意義明確時(shí)，分別用├、├n

、├+、├*表示├M

、├Mn、├M+、├M*。14第14頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)例2-2.例2-1所給的M1在處理輸入串的過(guò)程中經(jīng)歷的ID變換序列。

（1）處理輸入串000100的過(guò)程中經(jīng)歷的ID的變換序列如下：

q0000100├M0q000100├M00q00100 ├M000q0100├M0001q100├M00010q10 ├M000100q1├M000100Bq2

15第15頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)（2）處理輸入串0001的過(guò)程中經(jīng)歷的ID變換序列如下：

q00001├M0q0001├M00q001 ├M000q01├M0001q1├M0001Bq2（3）處理輸入串000101的過(guò)程中經(jīng)歷的ID變換序列如下：

q0000101├M0q000101├M00q00101 ├M000q0101├M0001q101├M00010q1116第16頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)（4）處理輸入串1的過(guò)程中經(jīng)歷的ID變換序列如下：

q01├M1q1├M1Bq2（5）處理輸入串00000的過(guò)程中經(jīng)歷的ID變換序列如下：

q000000├M0q00000├M00q0000 ├M000q000├M0000q00├M00000q0B17第17頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)

圖靈機(jī)接受的語(yǔ)言

L(M)={x|x∈∑*&q0x├M*α1qα2&q∈F&α1、α2∈Γ*}圖靈機(jī)接受的語(yǔ)言叫做遞歸可枚舉語(yǔ)言(recursivelyenumerablelanguage，r.e.)。如果存在圖靈機(jī)M=(Q,∑,Γ,δ,q0,B,F)，L=L(M)，并且對(duì)每一個(gè)輸入串x，M都停機(jī)，則稱(chēng)L為遞歸語(yǔ)言(recursivelylanguage)。

18第18頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)例2-3設(shè)有M2=({q0,q1,q2,q3},{0,1},{0,1,B},δ,q0,B,{q3})，其中δ的定義如下：δ(q0,0)=(q0,0,R)δ(q0,1)=(q1,1,R)δ(q1,0)=(q1,0,R)δ(q1,1)=(q2,1,R)δ(q2,0)=(q2,0,R)δ(q2,1)=(q3,1,R)19第19頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)

01Bq0(q0,0,R)(q1,1,R)

q1(q1,0,R)(q2,1,R)

q2(q2,0,R)(q3,1,R)

q3

20第20頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)為了弄清楚M2接受的語(yǔ)言，需要分析它的工作過(guò)程。（1）處理輸入串00010101的過(guò)程中經(jīng)歷的ID變換序列如下：q000010101├0q00010101├00q0010101├000q010101├0001q10101├00010q1101├000101q201├0001010q21├00010101q321第21頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)M2在q0狀態(tài)下，遇到0時(shí)狀態(tài)仍然保持為q0，同時(shí)將讀頭向右移動(dòng)一格而指向下一個(gè)符號(hào)；在q1狀態(tài)下遇到第一個(gè)1時(shí)狀態(tài)改為q1，并繼續(xù)右移讀頭，以尋找下一個(gè)1；在遇到第二個(gè)1時(shí)，動(dòng)作類(lèi)似，只是將狀態(tài)改為q2；當(dāng)遇到第三個(gè)1時(shí)，進(jìn)入終止?fàn)顟B(tài)q3，此時(shí)它正好掃描完整個(gè)輸入符號(hào)串，表示符號(hào)串被M2接受。

22第22頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)（2）處理輸入串1001100101100的過(guò)程中經(jīng)歷的ID變換序列如下：q01001100101100├1q1001100101100├

10q101100101100├100q11100101100├1001q2100101100├10011q300101100M2遇到第三個(gè)1時(shí)，進(jìn)入終止?fàn)顟B(tài)q3，輸入串的后綴00101100還沒(méi)有被處理。但是，由于M2已經(jīng)進(jìn)入終止?fàn)顟B(tài)，表示符號(hào)串1001100101100被M2接受。23第23頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)（3）處理輸入串000101000的過(guò)程中經(jīng)歷的ID變換序列如下：q0000101000├0q000101000├00q00101000├000q0101000├0001q101000├00010q11000├000101q2000├0001010q200├00010100q20├000101000q2B當(dāng)M2的ID變?yōu)?00101000q2B時(shí)，因?yàn)闊o(wú)法進(jìn)行下一個(gè)移動(dòng)而停機(jī),不接受輸入串000101000。24第24頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)M2接受的語(yǔ)言是字母表{0，1}上那些至少含有3個(gè)1的0、1符號(hào)串。請(qǐng)讀者考慮，如何構(gòu)造出接受字母表{0，1}上那些含且恰含有3個(gè)1的符號(hào)串的TM。

25第25頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)例2-4構(gòu)造TMM3，使L(M)={0n1n2n|n≥1}。分析：不能通過(guò)“數(shù)”0、1、或者2的個(gè)數(shù)來(lái)實(shí)現(xiàn)檢查。最為原始的方法來(lái)比較它們的個(gè)數(shù)是否是相同的：消除一個(gè)0、然后消除一個(gè)1，最后消除一個(gè)2。消除的0的帶方格上印刷一個(gè)X，在消除的1的帶方格上印刷一個(gè)Y，在消除的2的帶方格上印刷一個(gè)Z。26第26頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)正常情況下，輸入帶上的符號(hào)串的一般形式為

00…0011…1122…22TM啟動(dòng)后，經(jīng)過(guò)一段運(yùn)行，輸入帶上的符號(hào)串的一般情況為

X…X0…0Y…Y1…1Z…Z2…2BB需要給予邊界情況密切的關(guān)注。27第27頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.1基本圖靈機(jī)邊界情況X…XX…XY…YY…YZ…Z2…2BBX…XX…XY…Y1…1Z…Z2…2BBX…X0…0Y…YY…YZ…Z2…2BBX…X0…0Y…Y1…1Z…ZZ…ZBBX…X0…0Y…YY…YZ…ZZ…ZBB28第28頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月構(gòu)造思路

29第29頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月移動(dòng)函數(shù)

012XYZBq0(q0,X,R)

(q4,Y,R)

q1(q1,0,R)(q2,Y,R)

(q1,Y,R)

q2

(q2,1,R)(q3,Z,L)

(q2,Z,R)

q3(q3,0,L)(q3,1,L)

(q0,X,R)(q3,Y,L)(q3,Z,L)

q4

(q4,Y,R)(q4,Z,R)(q5,B,R)q5

30第30頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.2圖靈機(jī)作為非負(fù)整函數(shù)的計(jì)算模型

非負(fù)整數(shù)進(jìn)行編碼

——1進(jìn)制

用符號(hào)串0n表示非負(fù)整數(shù)n。用符號(hào)串表示k元函數(shù)f(n1,n2,…,nk)的輸入。如果f(n1,n2,…,nk)=m，則該圖靈機(jī)的輸出為0m。31第31頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.2圖靈機(jī)作為非負(fù)整函數(shù)的計(jì)算模型圖靈可計(jì)算的(Turingcomputable)設(shè)有k元函數(shù)f(n1,n2,…,nk)=m，TMM=(Q,∑,Γ,δ,q0,B,F)接受輸入串輸出符號(hào)串0m；當(dāng)f(n1,n2,…,nk)無(wú)定義時(shí)，TMM沒(méi)有恰當(dāng)?shù)妮敵鼋o出。稱(chēng)TMM計(jì)算k元函數(shù)f(n1,n2,…,nk)，也稱(chēng)f(n1,n2,…,nk)為T(mén)MM計(jì)算的函數(shù)。也稱(chēng)f是圖靈可計(jì)算的。

32第32頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.2圖靈機(jī)作為非負(fù)整函數(shù)的計(jì)算模型完全遞歸函數(shù)(totalrecursivefunction)設(shè)有k元函數(shù)f(n1,n2,…,nk)，如果對(duì)于任意的n1,n2,…,nk

，f均有定義，也就是計(jì)算f的圖靈機(jī)總能給出確定的輸出，則稱(chēng)f為完全遞歸函數(shù)。部分遞歸函數(shù)(partialrecursivefunction)圖靈機(jī)計(jì)算的函數(shù)稱(chēng)為部分遞歸函數(shù)。33第33頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.2圖靈機(jī)作為非負(fù)整函數(shù)的計(jì)算模型例2-5構(gòu)造TMM4，對(duì)于任意非負(fù)整數(shù)n，m，M4計(jì)算m+n。分析：M4的輸入為0n10m，輸出0n+m的符號(hào)串。n和m為0的情況需要特殊考慮。（1）當(dāng)n為0時(shí)，只用將1變成B就完成了計(jì)算，此時(shí)無(wú)需考察m是否為0；（2）當(dāng)m為0時(shí)，需要掃描過(guò)表示n的符號(hào)0，并將1改為B。（3）當(dāng)n和m都不為0時(shí)，我們需要將符號(hào)1改為0，并將最后一個(gè)0改為B。34第34頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月構(gòu)造思路

35第35頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月M4M4=({q0,q1,q2,q3},{0,1},{0,1,B},δ,q0,B,{q1})δ(q0，1)=(q1，B，R)δ(q0，0)=(q2，0，R)δ(q2，0)=(q2，0，R)δ(q2，1)=(q2，0，R)δ(q2，B)=(q3，B，L)δ(q3，0)=(q1，B，R)36第36頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.2圖靈機(jī)作為非負(fù)整函數(shù)的計(jì)算模型例2-6構(gòu)造圖靈機(jī)M5，對(duì)于任意非負(fù)整數(shù)n，m，M5計(jì)算如下函數(shù)：

n≥mn<m37第37頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月構(gòu)造思路

38第38頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月M5

M5=({q0,q1,q2,q3,q4,q5,q6,},{0,1},{0,1,X,B},δ,q0,B,{q6})δ(q0,0)=(q1,B,R)δ(q0,1)=(q5,B,R)δ(q1,0)=(q1,0,R)δ(q1,1)=(q1,1,R)δ(q1,X)=(q2,X,R)δ(q2,X)=(q2,X,R)δ(q2,0)=(q3,X,L)δ(q2,B)=(q4,B,L)δ(q3,X)=(q3,X,L)δ(q3,1)=(q3,1,L)δ(q3,0)=(q3,0,L)δ(q3,B)=(q0,B,R)39第39頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月M5δ(q4,X)=(q4,B,L)δ(q4,1)=(q6,0,R)δ(q5,X)=(q5,B,R)δ(q5,0)=(q5,B,R)δ(q5,B)=(q6,B,R)。40第40頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.1.3圖靈機(jī)的構(gòu)造

1.狀態(tài)的有窮存儲(chǔ)功能的利用2.多道(multi-track)技術(shù)

3.子程序(subroutine)技術(shù)

41第41頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月1.狀態(tài)的有窮存儲(chǔ)功能的利用例2-7構(gòu)造圖靈機(jī)M6，使得L(M6)={x|x∈{0,1}*&x中至多含3個(gè)1}。分析：M6只用記錄已經(jīng)讀到的1的個(gè)數(shù)。

q[0]表示當(dāng)前已經(jīng)讀到0個(gè)1；

q[1]表示當(dāng)前已經(jīng)讀到1個(gè)1；

q[2]表示當(dāng)前已經(jīng)讀到2個(gè)1；

q[3]表示當(dāng)前已經(jīng)讀到3個(gè)1。

42第42頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月1.狀態(tài)的有窮存儲(chǔ)功能的利用M6=({q[0],q[1],q[2],q[3],q[f]},{0,1},{0,1,B},δ,q[0],B,{q[f]})δ(q[0],0)=(q[0],0,R)δ(q[0],1)=(q[1],1,R)δ(q[0],B)=(q[f],B,R)δ(q[1],0)=(q[1],0,R)δ(q[1],1)=(q[2],1,R)δ(q[1],B)=(q[f],B,R)δ(q[2],0)=(q[2],0,R)δ(q[2],1)=(q[3],1,R)δ(q[2],B)=(q[f],B,R)δ(q[3],0)=(q[3],0,R)δ(q[3],B)=(q[f],B,R)43第43頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月1.狀態(tài)的有窮存儲(chǔ)功能的利用圖靈機(jī)是要接受且僅接受恰含3個(gè)1的0、1串的圖靈機(jī)，對(duì)M6進(jìn)行修改，得到M7

L(M7)={x|x∈{0,1}*&x中含且僅含3個(gè)1}M7=({q[0],q[1],q[2],q[3],q[f]},{0,1},{0,1,B},δ,q[0],B,{q[f]})44第44頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月L(M7)={x|x∈{0,1}*且x中僅含3個(gè)1}δ(q[0],0)=(q[0],0,R)δ(q[0],1)=(q[1],1,R)δ(q[1],0)=(q[1],0,R)δ(q[1],1)=(q[2],1,R)δ(q[2],0)=(q2),0,R)δ(q[2],1)=(q[3],1,R)δ(q[3],0)=(q[3],0,R)δ(q[3],B)=(q[f],B,R)45第45頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月L(M8)={x|x∈{0,1}*&x中至少含3個(gè)1}

M8=({q[0],q[1],q[2],q[f]},{0,1},{0,1,B},δ,q[0],B,{q[f]})δ(q[0],0)=(q[0],0,R)δ(q[0],1)=(q[1],1,R)δ(q[1],0)=(q[1],0,R)δ(q[1],1)=(q[2],1,R)δ(q[2],0)=(q[2],0,R)δ(q[2],1)=(q[f],1,R)

46第46頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月1.狀態(tài)的有窮存儲(chǔ)功能的利用例2-8構(gòu)造圖靈機(jī)M9它的輸入字母表為{0，1}，現(xiàn)在要求M9在它的輸入符號(hào)串的尾部添加子串101。分析：將待添加子串101存入窮控制器。首先找到符號(hào)串的尾部。將給定符號(hào)串中的符號(hào)依次地印刷在輸入帶上每印刷一個(gè)符號(hào)，就將它從有窮控制器的“存儲(chǔ)器”中刪去，當(dāng)該“存儲(chǔ)器”空時(shí)，圖靈機(jī)就完成了工作。47第47頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月1.狀態(tài)的有窮存儲(chǔ)功能的利用M9=({q[101],q[01],q[1],q[ε]},{0,1},{0,1,B},δ,q[101],B,{q[ε]})其中δ的定義為：δ(q[101],0)=(q[101],0,R)δ(q[101],1)=(q[101],1,R)δ(q[101],B)=(q[01],1,R)δ(q[01],B)=(q[1],0,R)δ(q[1],B)=(q[ε],1,R)48第48頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月1.狀態(tài)的有窮存儲(chǔ)功能的利用例2-9構(gòu)造圖靈機(jī)M10它的輸入字母表為{0，1}，要求M10在它的輸入符號(hào)串的開(kāi)始處添加子串101。將有窮控制器中的“存儲(chǔ)器”分成兩部分第一部分用來(lái)存放待添加的子串。第二部分用來(lái)存儲(chǔ)因添加符號(hào)串當(dāng)前需要移動(dòng)的輸入帶上暫時(shí)無(wú)帶方格存放的子串。一般形式為q[x,y]x待添加子串y當(dāng)前需要移動(dòng)的輸入帶上暫時(shí)無(wú)帶方格存放的子串。

49第49頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月1.狀態(tài)的有窮存儲(chǔ)功能的利用q[x,ε]為開(kāi)始狀態(tài)；q[ε,ε]為終止?fàn)顟B(tài)。設(shè)a、b為輸入符號(hào)δ(q[ax,y],b)=(q[x,yb],a,R)表示在沒(méi)有完成待插入子串的印刷之前，要將待插入子串的首字符印刷在TM當(dāng)前掃描的帶方格上。

50第50頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月1.狀態(tài)的有窮存儲(chǔ)功能的利用δ(q[ε,ay],b)=(q[ε,yb],a,R)表示當(dāng)完成待插入子串的插入工作之后，必須將插入點(diǎn)之后的子串順序地向后移動(dòng)。

δ(q[ε,ay],B)=(q[ε,y],a,R)

表示讀頭當(dāng)前所指的帶方格為空白，現(xiàn)將“存儲(chǔ)器”的第二部分中的當(dāng)前首符號(hào)a印刷在此帶方格上，同時(shí)將這個(gè)符號(hào)從存儲(chǔ)器中刪除。

51第51頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.多道(multi-track)技術(shù)

例2-10構(gòu)造M11，使L(M11)={xcy|x,y∈{0,1}+且x≠y}。分析：以符號(hào)c為分界線，逐個(gè)地將c前的符號(hào)與c后的符號(hào)進(jìn)行比較。當(dāng)發(fā)現(xiàn)對(duì)應(yīng)符號(hào)不同時(shí)，就進(jìn)入終止?fàn)顟B(tài)。當(dāng)發(fā)現(xiàn)x與y的長(zhǎng)度不相同而進(jìn)入終止?fàn)顟B(tài)。發(fā)現(xiàn)它們相同而停機(jī)。一個(gè)道存放被檢查的符號(hào)串，另一個(gè)存放標(biāo)記符。52第52頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月構(gòu)造思路

53第53頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.多道(multi-track)技術(shù)

M11=({q[ε],q[0],q[1],p[0],p[1],q,p,s,f},{[B,0],[B,1],[B,c]},{[B,0],[B,1],[B,c],[

,0],[

,1],[B,B]},δ,q[ε],[B,B],{f})

δ(q[ε],[B,0])=(q[0],[

,0],R)δ(q[ε],[B,1])=(q[1],[

,1],R)δ(q[a],[B,d])=(q[a],[B,d],R)δ(q[a],[B,c])=(p[a],[B,c],R)δ(p[a],[

,b])=(p[a],[

,b],R)δ(p[a],[B,a])=(p,[

,a],L)54第54頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.多道(multi-track)技術(shù)

δ(p,[

,b])=(p,[

,b],L)δ(p,[B,c])=(q,[B,c],L)δ(q,[B,a])=(q,[B,a],L)δ(q,[

,a])=(q[ε],[

,a],R)δ(p[a],[B,b])=(f,[B,b],R)δ(p[a],[B,B])=(p,[B,B],R)δ(s,[

,b])=(s,[

,b],R)δ(s,[B,a])=(f,[B,a],R) 55第55頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月3.子程序(subroutine)技術(shù)

將圖靈機(jī)的設(shè)計(jì)看成是一種特殊的程序設(shè)計(jì)，將子程序的概念引進(jìn)來(lái)。一個(gè)完成某一個(gè)給定功能的圖靈機(jī)M′從一個(gè)狀態(tài)q開(kāi)始，到達(dá)某一個(gè)固定的狀態(tài)f結(jié)束。將這兩個(gè)狀態(tài)作為另一個(gè)圖靈機(jī)M的兩個(gè)一般的狀態(tài)。當(dāng)M進(jìn)入狀態(tài)q時(shí)，相當(dāng)于啟動(dòng)M′(調(diào)用M′對(duì)應(yīng)的子程序)；當(dāng)M′進(jìn)入狀態(tài)f時(shí)，相當(dāng)于返回到M的狀態(tài)f。56第56頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月3.子程序(subroutine)技術(shù)

例2-11構(gòu)造M12完成正整數(shù)的乘法運(yùn)算。分析:設(shè)兩個(gè)正整數(shù)分別為m和n。輸入串為0n10m。輸出應(yīng)該為0n*m。算法思想：每次將n個(gè)0中的1個(gè)0改成B，就在輸入串的后面復(fù)寫(xiě)m個(gè)0。在M12的運(yùn)行過(guò)程中，輸入帶的內(nèi)容為

Bh0n-h10m10m*hB

57第57頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月正整數(shù)的乘法運(yùn)算（1）初始化。完成將第一個(gè)0變成B，并在最后一個(gè)0后寫(xiě)上1。我們用q0表示啟動(dòng)狀態(tài)，用q1表示完成初始化后的狀態(tài)。首先，消除前n個(gè)0中的第一個(gè)0，

q00n10m├+Bq10n-110m1（2）主控系統(tǒng)。從狀態(tài)q1開(kāi)始，掃描過(guò)前n個(gè)0中剩余的0和第一個(gè)1，將讀頭指向m個(gè)0的第一個(gè)，此時(shí)的狀態(tài)為q2。其ID變化為

Bhq10n-h10m10m*(h-1)B├+Bh0n-h1q20m10m*(h-1)B58第58頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月正整數(shù)的乘法運(yùn)算當(dāng)子程序完成m個(gè)0的復(fù)寫(xiě)后，回到q3。這個(gè)狀態(tài)相當(dāng)于子程序的返回（終止）狀態(tài)。然后在q3狀態(tài)下，將讀頭移回到前n個(gè)0中剩余的0中的第一個(gè)0，并將這個(gè)0改成B，進(jìn)入q1狀態(tài)，準(zhǔn)備進(jìn)行下一次循環(huán)

Bh0n-h1q30m10m*hB├+Bh+1q10n-h-110m10m*hB

59第59頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月正整數(shù)的乘法運(yùn)算當(dāng)完成m*n個(gè)0的復(fù)寫(xiě)之后，清除輸入帶上除了這m*n個(gè)0以外的其他非空白符號(hào)。q4為終止?fàn)顟B(tài)

Bnq110m10m*nB├+Bn+1+m+1q40m*nB（3）子程序。完成將m個(gè)0復(fù)寫(xiě)到后面的任務(wù)。從q2啟動(dòng)，到q3結(jié)束，返回到主控程序。Bh+10n-h-11q20m10m*hB├+Bh+10n-h-11q30m10m*h+1B

60第60頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2圖靈機(jī)的變形

從不同的方面對(duì)圖靈機(jī)進(jìn)行擴(kuò)充。雙向無(wú)窮帶圖靈機(jī)。多帶圖靈機(jī)。不確定的圖靈機(jī)。多維圖靈機(jī)等。它們與基本的圖靈機(jī)等價(jià)。

61第61頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.1雙向無(wú)窮帶圖靈機(jī)物理模型

62第62頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.1雙向無(wú)窮帶圖靈機(jī)雙向無(wú)窮帶(Turingmachinewithtwo-wayinfinitetape)

圖靈機(jī)M=(Q,∑,Γ,δ,q0,B,F)Q,∑,Γ,δ,q0,B,F的意義同定義9-1。Ｍ的即時(shí)描述ID同定義９-2。允許M的讀頭處在輸入串的最左端時(shí)，仍然可以向左移動(dòng)。63第63頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.1雙向無(wú)窮帶圖靈機(jī)M的當(dāng)前IDX1X2…Xi-1qXiXi+1…Xn

如果δ(q,Xi)=(p,Y,R)當(dāng)i≠1并且Y≠B時(shí)，M的下一個(gè)ID為

X1X2…Xi-1YpXi+1…Xn記作X1X2…Xi-1qXiXi+1…Xn├MX1X2…Xi-1YpXi+1…Xn表示M在IDX1X2…Xi-1qXiXi+1…Xn下，經(jīng)過(guò)一次移動(dòng)，將ID變成X1X2…Xi-1YpXi+1…Xn

。64第64頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.1雙向無(wú)窮帶圖靈機(jī)當(dāng)i=1并且Y=B時(shí)，M的下一個(gè)ID為

pX2…Xn記作

qX1X2…Xn├MpX2…Xn這就是說(shuō)，和基本圖靈機(jī)在讀頭右邊全部是B時(shí)，這些B不在ID中出現(xiàn)一樣，當(dāng)雙向無(wú)窮帶圖靈機(jī)的讀頭左邊全部是B時(shí)，這些B也不在該圖靈機(jī)的ID中出現(xiàn)。

65第65頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.1雙向無(wú)窮帶圖靈機(jī)如果δ(q,Xi)=(p,Y,L)當(dāng)i≠1時(shí)，M的下一個(gè)ID為

X1X2…pXi-1YXi+1…Xn記作X1X2…Xi-1qXiXi+1…Xn├MX1X2…pXi-1YXi+1…Xn表示M在IDX1X2…Xi-1qXiXi+1…n下，經(jīng)過(guò)一次移動(dòng)，將ID變成X1X2…pXi-1YXi+1…Xn。

66第66頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.1雙向無(wú)窮帶圖靈機(jī)當(dāng)i=1時(shí)，M的下一個(gè)ID為

pBYX2…Xn記作

qX1X2…Xn├MpBYX2…Xn表示M在IDqX1X2…Xn下，經(jīng)過(guò)一次移動(dòng)，將ID變成pBYX2…Xn。67第67頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.1雙向無(wú)窮帶圖靈機(jī)定理2-1對(duì)于任意一個(gè)雙向無(wú)窮帶圖靈機(jī)M，存在一個(gè)等價(jià)的基本圖靈機(jī)M′。證明要點(diǎn)：雙向無(wú)窮存儲(chǔ)的模擬：用一個(gè)具有2個(gè)道的基本TM來(lái)模擬：一個(gè)道存放M開(kāi)始啟動(dòng)時(shí)讀頭所注視的帶方格及其右邊的所有帶方格中存放的內(nèi)容；另一個(gè)道按照相反的順序存放開(kāi)始啟動(dòng)時(shí)讀頭所注視的帶方格左邊的所有帶方格中存放的內(nèi)容。雙向移動(dòng)的模擬：在第1道上，移動(dòng)的方向與原來(lái)的移動(dòng)方向一致，在第2道上，移動(dòng)的方向與原來(lái)的移動(dòng)方向相反。

68第68頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月用單向無(wú)窮帶模擬雙向無(wú)窮帶

69第69頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.2多帶圖靈機(jī)多帶圖靈機(jī)(multi-tapeturingmachine)

允許圖靈機(jī)有多個(gè)雙向無(wú)窮帶，每個(gè)帶上有一個(gè)相互獨(dú)立的讀頭。

k帶圖靈機(jī)在一次移動(dòng)中完成如下三個(gè)動(dòng)作

⑴改變當(dāng)前狀態(tài)；⑵各個(gè)讀頭在自己所注視的帶方格上印刷一個(gè)希望的符號(hào)。⑶各個(gè)讀頭向各自希望的方向移動(dòng)一個(gè)帶方格。70第70頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.2多帶圖靈機(jī)71第71頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.2多帶圖靈機(jī)定理2-2多帶圖靈機(jī)與基本的圖靈機(jī)等價(jià)。證明要點(diǎn)：對(duì)一個(gè)k帶圖靈機(jī)，用一條具有2k道的雙向無(wú)窮帶圖靈機(jī)M′，實(shí)現(xiàn)對(duì)這個(gè)k帶圖靈機(jī)M的模擬。對(duì)應(yīng)M的每一條帶，M′用兩個(gè)道來(lái)實(shí)現(xiàn)模擬。其中一條道用來(lái)存放對(duì)應(yīng)的帶的內(nèi)容，另一條道專(zhuān)門(mén)用來(lái)標(biāo)記對(duì)應(yīng)帶上的讀頭所在的位置。

72第72頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.3不確定的圖靈機(jī)不確定圖靈機(jī)與基本圖靈機(jī)的區(qū)別是對(duì)于任意的(q，X)∈Q×Γ，δ(q，X)={(q1，Y1，D1)，(q2，Y2，D2)，…，(qk，Yk，Dk)}Dj為讀頭的移動(dòng)方向。即Dj∈{R，L}。表示M在狀態(tài)q，讀到X時(shí)，可以有選擇地進(jìn)入狀態(tài)qj，印刷字符Yj，按Dj移動(dòng)讀頭

L(M)={w|w∈∑*且ID1├*IDn，且IDn含M的終止?fàn)顟B(tài)}。73第73頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.3不確定的圖靈機(jī)定理2-3不確定的圖靈機(jī)與基本的圖靈機(jī)等價(jià)證明要點(diǎn)：讓等價(jià)的基本圖靈機(jī)M′具有3條帶。第1條帶用來(lái)存放輸入。第2條帶上系統(tǒng)地生成M的各種可能的移動(dòng)序列M′在第3條帶上按照第2條帶上給出的移動(dòng)系列處理輸入串，如果成功，則接受之，如果不成功，則在第2條帶上生成下一個(gè)可能的移動(dòng)系列，開(kāi)始新一輪的“試處理”。74第74頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.4多維圖靈機(jī)多維圖靈機(jī)(multi-dimensionalTuringmachine)讀頭可以沿著多個(gè)維移動(dòng)。

k維圖靈機(jī)(k-dimensionalTuringmachine)圖靈機(jī)可以沿著k維移動(dòng)。k維圖靈機(jī)的帶由k維陣列組成，而且在所有的2k個(gè)方向上都是無(wú)窮的，它的讀頭可以向著2k個(gè)方向中的任一個(gè)移動(dòng)。75第75頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.4多維圖靈機(jī)

定理2-4多維圖靈機(jī)與基本圖靈機(jī)等價(jià)。用一維的形式表示k維的內(nèi)容，就像多維數(shù)組在計(jì)算機(jī)的內(nèi)存中都被按照一維的形式實(shí)現(xiàn)存儲(chǔ)一樣。段(Segment)用來(lái)表是一維上的內(nèi)容。用#作為段分割符。￠用作該字符串的開(kāi)始標(biāo)志，$用作該字符串的結(jié)束標(biāo)志。

76第76頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月基本圖靈機(jī)模擬2維圖靈機(jī)

Ba1a2a3a4BBBBBBBa5Ba6a7a8a9a10BBBBa11BBBBa12Ba13Ba14a15a16BBBBBBBBa16BBBa17BBBBBa18Ba19a20BBBBBBBBBBBBBBBBBBBa2177第77頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月基本圖靈機(jī)模擬2維圖靈機(jī)￠Ba1a2a3a4BBBBBB#Ba5Ba6a7a8a9a10BBB#Ba11BBBBa12Ba13Ba14#a15a16BBBBBBBBa16#BBBa17BBBBBa18B#a19a20BBBBBBBBB#BBBBBBBBBBa21$78第78頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.2.5其他圖靈機(jī)

1.多頭TM2.離線TM3.作為枚舉器的TM4.多棧機(jī)5.計(jì)數(shù)機(jī)6.Church-Turing論題與隨機(jī)存取機(jī)79第79頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月1.多頭圖靈機(jī)多頭圖靈機(jī)(multi-headTuringmachine)指在一條帶上有多個(gè)讀頭，它們受M的有窮控制器的統(tǒng)一控制，M根據(jù)當(dāng)前的狀態(tài)和這多個(gè)頭當(dāng)前讀到的字符確定要執(zhí)行的移動(dòng)。在M的每個(gè)動(dòng)作中，各個(gè)讀頭所印刷的字符和所移動(dòng)的方向都可以是相互獨(dú)立的。80第80頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月1.多頭圖靈機(jī)定理2-5多頭圖靈與基本的圖靈機(jī)等價(jià)。可以用一條具有k+1個(gè)道的基本圖靈機(jī)來(lái)模擬一個(gè)具有k個(gè)頭的圖靈（k頭圖靈機(jī)）。其中一個(gè)道用來(lái)存放原輸入帶上的內(nèi)容，其余k個(gè)道分別用來(lái)作為k個(gè)讀頭位置的標(biāo)示。

81第81頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.離線圖靈機(jī)離線圖靈機(jī)(off-lineTuringmachine)有一條輸入帶是只讀帶(read-onlytape)的多帶圖靈機(jī)。符號(hào)￠和$用來(lái)限定它的輸入串存放區(qū)域，￠在左邊，$在右邊。不允許該帶上的讀頭移出由￠和$限定的區(qū)域——離線的圖靈機(jī)。如果只允許只讀帶上的讀頭從左向右移動(dòng)，則稱(chēng)之為在線圖靈機(jī)(on-lineTuringmachine)。

82第82頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.離線圖靈機(jī)定理2-6離線圖靈機(jī)與基本的圖靈機(jī)等價(jià)。證明要點(diǎn)：讓模擬M的離線圖靈機(jī)比M多一條帶，并且用這多出來(lái)的帶復(fù)制M的輸入串。然后將這條帶看作是M的輸入帶，模擬M進(jìn)行相應(yīng)的處理。

83第83頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月3.作為枚舉器的圖靈機(jī)作為枚舉器的圖靈機(jī)(Turingmachineasenumerator)多帶圖靈機(jī)，其中有一條帶專(zhuān)門(mén)作為輸出帶，用來(lái)記錄產(chǎn)生語(yǔ)言的每一個(gè)句子。在枚舉器中，一旦一個(gè)字符被寫(xiě)在了輸出帶上，它就不能被更改。如果該帶上的讀頭的正常移動(dòng)方向是向右移動(dòng)的話，這個(gè)帶上的讀頭是不允許向左移動(dòng)的。如果這個(gè)語(yǔ)言有無(wú)窮多個(gè)句子，則它將永不停機(jī)。它每產(chǎn)生一個(gè)句子，就在其后打印一個(gè)分割符“#”。枚舉器產(chǎn)生的語(yǔ)言記為G(M)。

84第84頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月3.作為枚舉器的圖靈機(jī)規(guī)范的順序(canonicalorder)定理2-7L為遞歸可枚舉語(yǔ)言的充分必要條件是存在一個(gè)圖靈機(jī)M，使得L=G(M)。定理2-8一個(gè)語(yǔ)言L為遞歸語(yǔ)言的充分必要條件是存在一個(gè)圖靈機(jī)M，使得L=G(M)，并且L是被M按照規(guī)范順序產(chǎn)生的。

85第85頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月4.多棧機(jī)多棧機(jī)(multi-stackmachines)是一個(gè)擁有一條只讀輸入帶和多條存儲(chǔ)帶的不確定圖靈機(jī)。多棧機(jī)的只讀帶上的讀頭不能左移。存儲(chǔ)帶上的讀頭可以向左和向右移動(dòng)。右移時(shí)，一般都在當(dāng)前注視的帶方格上印刷一個(gè)非空白字符。左移時(shí)，必須在當(dāng)前注視的帶方格中印刷空白字符B。一個(gè)確定的雙棧機(jī)(doublestackmachines)是一個(gè)確定的圖靈機(jī)，它具有一條只讀的輸入帶和兩條存儲(chǔ)帶。存儲(chǔ)帶上的讀頭左移時(shí)，只能印刷空白符號(hào)B

。86第86頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月4.多棧機(jī)下推自動(dòng)機(jī)是一種非確定的多帶圖靈機(jī)。它有一條只讀的輸入帶，一條存儲(chǔ)帶。定理2-9一個(gè)任意的單帶圖靈機(jī)可以被一個(gè)確定的雙棧機(jī)模擬。87第87頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月5.計(jì)數(shù)機(jī)計(jì)數(shù)機(jī)(countermachine)有一條只讀輸入帶和若干個(gè)用于計(jì)數(shù)的單向無(wú)窮帶的離線圖靈機(jī)。擁有n個(gè)用于計(jì)數(shù)帶的計(jì)數(shù)機(jī)被稱(chēng)為n計(jì)數(shù)機(jī)。用于計(jì)數(shù)的帶上僅有兩種字符，一個(gè)為相當(dāng)于是作為棧底符號(hào)的Z，該字符也可以看作是計(jì)數(shù)帶的首符號(hào)，它僅出現(xiàn)在計(jì)數(shù)帶的最左端；另一個(gè)就是空白符B。這個(gè)帶上所記的數(shù)就是從Z開(kāi)始到讀頭當(dāng)前位置所含的B的個(gè)數(shù)。

定理2-10圖靈機(jī)可以被一個(gè)雙計(jì)數(shù)機(jī)模擬。

88第88頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月6.丘奇-圖靈論題與隨機(jī)存取機(jī)對(duì)于任何可以用有效算法解決的問(wèn)題，都存在解決此問(wèn)題的圖靈機(jī)。隨機(jī)存取機(jī)(randomaccessmachine，RAM)含有無(wú)窮多個(gè)存儲(chǔ)單元，這些存儲(chǔ)單元被按照0、1、2、…進(jìn)行編號(hào)，每個(gè)存儲(chǔ)單元可以存放一個(gè)任意的整數(shù)；有窮個(gè)能夠保存任意整數(shù)的算術(shù)寄存器。這些整數(shù)可以被譯碼成通常的各類(lèi)計(jì)算機(jī)指令。定理2-11如果RAM的基本指令都能用圖靈機(jī)來(lái)實(shí)現(xiàn)，那么就可以用圖靈機(jī)實(shí)現(xiàn)RAM。89第89頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.3通用圖靈機(jī)

通用圖靈機(jī)(universalTuringmachine)實(shí)現(xiàn)對(duì)所有圖靈機(jī)的模擬。編碼系統(tǒng)它可以在實(shí)現(xiàn)對(duì)圖靈機(jī)的表示的同時(shí)，實(shí)現(xiàn)對(duì)該TM處理的句子的表示。用0和1對(duì)這些除空白符以外的其他的帶符號(hào)進(jìn)行編碼。同時(shí)也可以用0和1對(duì)圖靈機(jī)的移動(dòng)函數(shù)進(jìn)行編碼。90第90頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.3通用圖靈機(jī)

M=({q1,q2,…,qn},{0，1},{0，1，B},δ,q1,B,{q2})

用X1、X2、X3分別表示0、1、B，用D1、D2分別表示R、L。

δ(qi,Xj)=(qk,Xl,Dm)可以用0i10j10k10l10m表示。91第91頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.3通用圖靈機(jī)

圖靈機(jī)M可用

111code111code211……11coder111codet

是動(dòng)作δ(qi,Xj)=(qk,Xl,Dm)的形如0i10j10k10l10m的編碼。

圖靈機(jī)M和它的輸入串w則可以表示成

111code111code211……11coder111w

按照規(guī)范順序分別對(duì)表示圖靈機(jī)的符號(hào)行和表示輸入的符號(hào)行進(jìn)行排序。

92第92頁(yè)，課件共102頁(yè)，創(chuàng)作于2023年2月2.3通用圖靈機(jī)

Ld={w|w是第j個(gè)句子，并且第j個(gè)圖靈機(jī)不接受它}不是遞歸可枚舉語(yǔ)言。通用語(yǔ)言(universallanguage)Lu={<M，w>|M接受w}<M，w>為如下形式的串，表示圖靈機(jī)M=({q1,q2,…,qn},{0，1},{0，1，B},δ,q1,B,{q2})和它的輸入串w。

111code11