丘奇-圖靈論題.ppt

1、1,樸秀峰 ,計(jì)算理論,第3章 丘奇-圖靈論題,2,引言,什么是計(jì)算？ 計(jì)算機(jī)的基本能力和局限性是什么？,3,引言,計(jì)算機(jī)科學(xué)歷史上關(guān)于概念的爭(zhēng)論,什么是計(jì)算 什么是操作系統(tǒng) 基本上解決 什么internet ? 什么是數(shù)據(jù)庫(kù) 什么是數(shù)據(jù)倉(cāng)庫(kù) 還在爭(zhēng)論 什么是數(shù)據(jù)網(wǎng)格 解決方法， 給出大眾能理解的代表,4,引言,計(jì)算機(jī)科學(xué)歷史上關(guān)于概念的爭(zhēng)論,解決的辦法， 給出一個(gè)代表 什么是 3的倍數(shù) 3N |N=1,2,3, x| x mod 3 =0 代表元 ：3 什么是操作系統(tǒng) 代表元：Windows, Unix 什么internet 代表元：大眾理解：Web ， IE 什么是計(jì)算? 多個(gè)模型；代表元

2、：圖靈機(jī), 或 遞歸函數(shù)論,5,引言,在還沒(méi)有計(jì)算機(jī)的時(shí)候， 憑想象力把后來(lái)出現(xiàn)的 把計(jì)算機(jī)的理論模型建立起來(lái)了。 1936年 想得如此周到、嚴(yán)密 好像從高度文明的外星來(lái)的文化使者,6,引言,Alan M. Turing (19121954),In 1936, Turing introduced hisabstract model for computation inhis article “On Computable Numbers,”.,At the same time, Alonzo Church published similar ideas and results. 殊途同歸,Tur

3、ing model 成為理論計(jì)算科學(xué)的標(biāo)準(zhǔn)模型standard model,7,引言,圖靈機(jī)（Turing Machine，TM），是計(jì)算機(jī)的一種簡(jiǎn)單的數(shù)學(xué)模型。 歷史上，馮諾曼計(jì)算機(jī)的產(chǎn)生就是由圖靈機(jī)誘發(fā)的。 丘奇圖靈論題：一切合理的計(jì)算模型都等同于圖靈機(jī).,8,主要內(nèi)容,3.1 丘奇圖靈論題 3.1.1 圖靈機(jī)的形式化定義 3.1.2 圖靈機(jī)的例子 3.2 圖靈機(jī)的變形 3.2.1 多帶圖靈機(jī) 3.2.2 非確定型圖靈機(jī) 3.2.3 枚舉器 3.2.4 與其他模型的等價(jià)性 3.3 算法的定義 3.3.1 希爾伯特問(wèn)題 3.3.2 描述圖靈機(jī)的術(shù)語(yǔ),9,3.1 圖靈機(jī)(Turning Mac

4、hine),非形式化描述,根據(jù)當(dāng)前狀態(tài)和字符 xi ，決定 寫 移 轉(zhuǎn)三動(dòng)作 -寫 letter, 有存儲(chǔ)器- 左或右移動(dòng) 轉(zhuǎn)移狀態(tài) 可以作循環(huán)語(yǔ)句 磁帶相當(dāng)于數(shù)組，可讀寫。這是增加的重要資源,每一步，讀寫頭在單向無(wú)窮帶上左右移動(dòng)并讀寫。,10,圖靈機(jī),state q0,初始, 帶子上只有輸入串w*,其它地方是空的。開(kāi)始狀態(tài) q0。,計(jì)算過(guò)程中讀寫頭左右移動(dòng)，機(jī)器內(nèi)部狀態(tài)改變，帶子上內(nèi)容重寫。,數(shù)組結(jié)構(gòu),11,圖靈機(jī),輸出約定,三種輸出：接受、拒絕、循環(huán),非常規(guī)意義循環(huán)不停機(jī) 引出可判定性,12,圖靈機(jī)與有限自動(dòng)機(jī),狀態(tài) 控制器,相似性：有限狀態(tài)集 區(qū)別： (1)圖靈機(jī)在帶子上既能讀也能寫。

5、(2)圖靈機(jī)的讀寫頭既能向左也能向右移動(dòng)。 (3)圖靈機(jī)的帶子是無(wú)限長(zhǎng)的。 (4)圖靈機(jī)進(jìn)入拒絕和接受狀體將立即停機(jī)。,13,圖靈機(jī),考慮圖靈機(jī) M1，它檢查語(yǔ)言 B = w#w | w0,1* 的成員關(guān)系。即設(shè)計(jì) M1，使得如果輸入是 B 的成員，它就接受，否則拒絕。 M1=“對(duì)于輸入字符串 w (1) 在 # 兩邊對(duì)應(yīng)的位置上來(lái)回移動(dòng)，檢查這些對(duì)應(yīng)位置是否包含相同的符號(hào)，如不是，或者沒(méi)有 #，則拒絕，為跟蹤對(duì)應(yīng)的符號(hào)，消去所有檢查過(guò)的符號(hào)。 (2) 當(dāng) # 左邊的所有符號(hào)都被消去時(shí)，檢查 # 右側(cè)是否還有符號(hào)，如果有則拒絕，否則接受。”,14,M1 的運(yùn)行示意圖,M,Tape head m

6、oves to right,15,M1 的運(yùn)行示意圖,M,Tape head moves to left,16,M1 的運(yùn)行示意圖,M,Tape head moves to right,17,M1 的運(yùn)行示意圖,M,Tape head moves to left,18,M1 的運(yùn)行示意圖,M,Tape head moves to right,19,M1 的運(yùn)行示意圖,M,Tape head moves to left,20,M1 的運(yùn)行示意圖,M,accept,Tape head moves to right,21,圖靈機(jī)的形式化定義,定義 3.1,圖靈機(jī)是一個(gè) 7 元組 (Q, , , ,

7、q0, qaccept, qreject) (1) Q 是狀態(tài)集。 (2) 是輸入字母表，不包括特殊空白符號(hào)。 (3) 是帶字母表，其中 并且 。 (4) : Q Q L, R 是轉(zhuǎn)移函數(shù)。 (5) q0 是起始狀態(tài)。 (6) qaccept 是接受狀態(tài)。 (7) qreject 是拒絕狀態(tài)，qacceptqreject。,例如: (q, a) = (r, b, L),22,圖靈機(jī)的計(jì)算方式,開(kāi)始時(shí)，M 以最左邊的 n 個(gè)帶方格接收輸入w=w1w2wn *，帶的其余部分保持空白(即填以空白符)，讀寫頭從最左邊的帶方格開(kāi)始運(yùn)行，注意 不含空字符，故出現(xiàn)在帶上的第一個(gè)空字符表示輸入的結(jié)束。 M 開(kāi)

8、始運(yùn)行后，計(jì)算根據(jù)轉(zhuǎn)移函數(shù)所描述的規(guī)則進(jìn)行，如果 M 試圖將讀寫頭從帶的最左端再向左移出，即使轉(zhuǎn)移函數(shù)指示的是 L，讀寫頭也停在原地不動(dòng)。計(jì)算一直持續(xù)到它進(jìn)入接受狀態(tài)或拒絕狀態(tài)，此時(shí)停機(jī)，如果二者都不發(fā)生，則 M 將永遠(yuǎn)運(yùn)行下去。,23,圖靈機(jī)的格局,圖靈機(jī)計(jì)算過(guò)程中，當(dāng)前狀態(tài)、當(dāng)前帶內(nèi)容和讀寫頭當(dāng)前位置組合在一起，稱為圖靈機(jī)的格局。 對(duì)于狀態(tài) q 和帶字母表 的兩個(gè)字符串 u 和 v，以 uqv 表示如下格局：當(dāng)前狀態(tài)是 q，當(dāng)前帶上的內(nèi)容是 uv，讀寫頭的當(dāng)前位置是 v 的第一個(gè)符號(hào)，帶上 v 的字符最后字符以后的符號(hào)都是空白符。 例如，1011q701111,q7,24,圖靈機(jī)計(jì)算方式的

9、形式化,如果圖靈機(jī)能合法地從格局 C1 一步進(jìn)入 C2，則稱格局 C1產(chǎn)生格局 C2。 設(shè) a, b 和 c 是 中的符號(hào)，u 和 v 是 * 中字符串，qi 和 qj是狀態(tài)，則 uaqibv 和 uqjacv 是兩個(gè)格局。如果轉(zhuǎn)移函數(shù)滿足 (qi , b) = (qj , c, L)，則說(shuō)uaqibv 產(chǎn)生和 uqjacv 。 M 在輸入 w 上的起始格局是格局 q0w，表示機(jī)器處于起始狀態(tài) q0，并且讀寫頭處于帶子的最左端位置，在接受格局里，狀態(tài)是 qaccept ，在拒絕格局里，狀態(tài)是 qreject。接受和拒絕狀態(tài)都是停機(jī)狀態(tài)，它們都不再產(chǎn)生新的格局。 由于圖靈機(jī)只在接受或拒絕狀態(tài)下才

10、停機(jī)，可以等價(jià)地將狀態(tài)轉(zhuǎn)移函數(shù)簡(jiǎn)化 : Q Q L, R 其中 Q 是取消 qaccept 和qreject 的 Q。,25,圖靈機(jī)計(jì)算方式的形式化,圖靈機(jī) M 接受輸入 w ，如果存在格局的序列 Cl, C2, , Ck使得： (1) Cl 是 M 在輸入 w 上的起始格局； (2) 每一個(gè)Ci 產(chǎn)生 Ci +1； (3) Ck 是接受格局。 M 接受的字符串的集合稱為 M 的語(yǔ)言，或被 M 識(shí)別的語(yǔ)言，記為 L(M)。,26,圖靈機(jī)的形式化定義,定義 3.2,如果一個(gè)語(yǔ)言能被某一圖靈機(jī)識(shí)別，則稱該語(yǔ)言是圖靈可識(shí)別的 (Turning recognizable)。 也稱為遞歸可枚舉語(yǔ)言。,輸

11、入上運(yùn)行一個(gè)TM時(shí)，可能出現(xiàn)三種結(jié)果： 接受、拒絕、循環(huán)（僅僅指機(jī)器不停機(jī)） 對(duì)于一個(gè)輸入，TM有兩種方式不接受它： 一種拒絕狀態(tài) 一種進(jìn)入循環(huán) 問(wèn)題：如何區(qū)別長(zhǎng)計(jì)算 與 死循環(huán)？,因此，我們喜歡對(duì)所有輸入都停機(jī)的圖靈機(jī)，永不循環(huán)，這種機(jī)器為判定器。因?yàn)樗鼈兛偰軟Q定是接受還是拒絕。,27,圖靈機(jī)的形式化定義,定義 3.3,如果一個(gè)語(yǔ)言能被某一圖靈機(jī)判定，則稱該語(yǔ)言是圖靈可判定的 (Turning decidable)。 也稱為遞歸語(yǔ)言。,可識(shí)別與可判定？ 1.可識(shí)別接受該語(yǔ)言； 2.可判定可以不接受該語(yǔ)言。,28,圖靈機(jī)舉例,例3.4 描述 TM M2，它識(shí)別的語(yǔ)言是所有由 0 組成、長(zhǎng)度為

12、2的方冪的字符串，即 A= | n 0,M2 = “對(duì)于輸入字符串w： 1) 從左往右掃描整個(gè)帶子，隔一個(gè)字符消去一個(gè)0。 2) 如果在第1步之后，帶子上只剩下唯一的一個(gè)0，則接受。 3) 如果在第1步之后，帶子上包含不止一個(gè)0，并且0的個(gè)數(shù)是奇數(shù)，則拒絕。 4) 讀寫頭返回至帶子的最左端。 5) 轉(zhuǎn)到第1步?！?29,圖靈機(jī)舉例,q1,q3,q4,qreject,q2,qaccept,q5,0 , R,R xR,R,0 x, R,xR,xR,L,0R,xR,R,0 x, R,xL 0L,R,30,圖靈機(jī)的例子,每重復(fù)一次第 1 步，消去了一半個(gè)數(shù)的 0。由于在第 1 步中，機(jī)器掃描了整個(gè)帶子

13、，故它能夠知道它看到的 0 的個(gè)數(shù)是奇數(shù)還是偶數(shù)，如果是大于 1 的奇數(shù)，則輸入中所含的 0 的個(gè)數(shù)不可能是 2 的方冪，此時(shí)機(jī)器就拒絕。但是，如果看到的 0 的個(gè)數(shù)是 1，則輸入中所含的 0 的個(gè)數(shù)肯定是 2 的方冪，此時(shí)機(jī)器就接受。 M2= (Q, , , , q1, qaccept, qreject)的形式化描述： Q=q1 , q2 , q3 , q4 , q5 , qaccept, qreject， =0， =0 , x , ， 將描述成狀態(tài)圖 開(kāi)始、接受和拒絕狀態(tài)分別是q1, qaccept, qreject,31,圖靈機(jī)舉例,例3.5 下面給出圖靈機(jī) M1 形式化描述 M1= (

14、Q, , , , q1, qaccept, qreject)， 它的判定語(yǔ)言是 B = w#w | w 0, 1* 。,Q = q1, q2, , q8 , qaccept, qreject ， = 0, 1, # 且 = 0, 1, #, x, 。 用狀態(tài)圖描述 。 開(kāi)始、接受和拒絕狀態(tài)分別是 q1, qaccept, qreject。,32,圖靈機(jī)M1的狀態(tài)圖,q1,q8,q3,q5,q6,q4,q7,qaccept,q2,#R,xR,R,0,1R,#R,xR,0,1,xL,0,1L,#L,xR,1x,L,1x,R,0 x,L,#R,0 x,R,0,1R,xR,第一步由q1 到 q7 實(shí)現(xiàn)

15、，第二步由其余狀態(tài)實(shí)現(xiàn),33,圖靈機(jī)舉例,例3.6 圖靈機(jī) M3 做一些初等算術(shù)，它判定的語(yǔ)言 C = aibjck | i j = k，且 i, j, k 1,M3=“對(duì)于輸入字符串 w： 1) 從左往右掃描輸入，確認(rèn)輸入具有形式 a*b*c*，否則拒絕。 2) 讀寫頭回到帶子的左端點(diǎn)。 3) 消去一個(gè) a，并向右掃描直到 b 出現(xiàn)。在 b 與 c 之間來(lái)回移動(dòng)，成對(duì)地消去 b 和 c，直到把所有的 b 都消去。如果 c 全消除后還有 b，則拒絕。 4) 如果還有 a 未消去，則恢復(fù)所有已消去的 b，再重復(fù)第 3步。如果所有的 a 都已被消去，則檢查所有的 c 是否都已被消去。如果是，則接受

16、，否則拒絕?！?34,圖靈機(jī)舉例,例3.7 圖靈機(jī) M4 解所謂的元素區(qū)分問(wèn)題。給出一列 0, 1 組成的字符串系列，字符串之間用符號(hào) # 隔開(kāi)，M4 的任務(wù)是：如果此序列中的所有字符串都不同，則接受。 此語(yǔ)言是： E= #x1 #x2 #xl，xi 0,1*, 且對(duì)任意 i j， xi xj ,機(jī)器 M4 將 x1 與 x2 到 xl 進(jìn)行比較，然后將 x2 與 x3 到 xl 進(jìn)行比較，依此類推。M4 的非形式描述如下。,35,圖靈機(jī)舉例,M4=“對(duì)于輸入的 w： 1) 在最左端的帶符號(hào)的頂上做個(gè)記號(hào)。如果此帶符號(hào)是空白符，則接受。如果此符號(hào)是 #，則進(jìn)行下一步。否則，拒絕。 2) 向右掃

17、描下一個(gè) #，并在其頂上做第二個(gè)記號(hào)。如果在遇到空白符之前沒(méi)有遇到 #，則帶上只有 x1 ，因此接受。 3) 通過(guò)來(lái)回移動(dòng)，比較做了記號(hào)的 # 的右邊的兩個(gè)字符串，如果它們相等，則拒絕。 4) 將兩個(gè)記號(hào)中右邊的那個(gè)向右移到下一個(gè) # 上。如果在碰到空白符之前沒(méi)有遇到 #，則將左邊的記號(hào)向右移到下一個(gè) # 上，并且將右邊記號(hào)移到后面的 # 上。如果這時(shí)右邊記號(hào)還找不到 #，則所有的字符串都已經(jīng)比較過(guò)了，因而接受。 5) 轉(zhuǎn)到第 3 步繼續(xù)執(zhí)行?！?36,主要內(nèi)容,3.1 丘奇圖靈論題 3.1.1 圖靈機(jī)的形式化定義 3.1.2 圖靈機(jī)的例子 3.2 圖靈機(jī)的變形 3.2.1 多帶圖靈機(jī) 3.2

18、.2 非確定型圖靈機(jī) 3.2.3 枚舉器 3.2.4 與其他模型的等價(jià)性 3.3 算法的定義 3.3.1 希爾伯特問(wèn)題 3.3.2 描述圖靈機(jī)的術(shù)語(yǔ),37,圖靈機(jī)的變形,從不同的方面對(duì) TM 進(jìn)行擴(kuò)充。 雙向無(wú)窮帶 TM 允許 TM 的輸入帶是無(wú)窮的。 多帶 TM 允許 TM 有多于一條的輸入帶。此時(shí)每條帶上將有一個(gè)讀頭。 不確定的 TM 允許 TM 在某一狀態(tài)下根據(jù)讀入的符號(hào)選擇地進(jìn)行某一個(gè)動(dòng)作：進(jìn)入某個(gè)狀態(tài)，在讀頭的當(dāng)前位置印刷某個(gè)符號(hào)，將讀頭移向某個(gè)方向。 多維 TM 相當(dāng)于在雙向 TM 的基礎(chǔ)上進(jìn)一步擴(kuò)充，允許TM 的“輸入帶”向更多的方向延伸。 枚舉器允許圖靈機(jī)帶有打印機(jī)。 它們與基

19、本的 TM 等價(jià)。 在形式變化中保持不變的性質(zhì)稱為穩(wěn)健性。,38,多帶圖靈機(jī),多帶圖靈機(jī) (multitape Turing Machine) 很像普通圖靈機(jī)，只是有多個(gè)帶子，每個(gè)帶子都有自己的讀寫頭，用于讀和寫。開(kāi)始時(shí)，輸入出現(xiàn)在第一個(gè)帶子上，其它的帶子都是空白。轉(zhuǎn)移函數(shù)改為允許多個(gè)帶子同時(shí)進(jìn)行讀、寫和移動(dòng)讀寫頭，其形式為： ： Qk QkL, R, Sk 此處 k 是帶子的個(gè)數(shù)。表達(dá)式 ( qi , a1 , a2 , , ak ) = ( qj, b1, b2, , bk , L, R, , L) 指的是：若機(jī)器處于狀態(tài) qi ，讀寫頭 1 到 k 所讀的符號(hào)分別是 a1 到 ak ，則

20、機(jī)器轉(zhuǎn)移到狀態(tài) qj，各讀寫頭分別寫下符號(hào) b1 到 bk，且按此式所指示的那樣移動(dòng)每個(gè)讀寫頭。,39,多帶圖靈機(jī),將一 個(gè)多帶 TM M 轉(zhuǎn)換為一個(gè)與之等價(jià)的單帶 TM S，關(guān)健是怎樣用 S 來(lái)模擬 M。 假設(shè) M 有 k 個(gè)帶子。 S 把此 k 個(gè)帶子的信息都存儲(chǔ)在它的唯一帶子上，并以此來(lái)模擬 k 個(gè)帶子的效果，它用一個(gè)新的符號(hào) # 作為定界符，以分開(kāi)不同帶子的內(nèi)容。除了帶內(nèi)容之外，S 還必須記錄讀寫頭的位置。為此，它在一個(gè)符號(hào)的頂上加個(gè)點(diǎn)，以此來(lái)標(biāo)記讀寫頭在其帶上的位置。S 把它們想象為虛擬帶子和虛擬讀寫頭。像以前一樣，加點(diǎn)的帶符號(hào)應(yīng)是已經(jīng)加進(jìn)帶字母表的新符號(hào)。,40,多帶圖靈機(jī),41,

21、多帶圖靈機(jī),S = “對(duì)于輸入 w=w1 wn： 1) S 在白己的帶子上放入 #w1w2wn# # # #（上邊沒(méi)加點(diǎn)） 此格式表示了 M 的全部 k 個(gè)帶子的內(nèi)容。 2)為了模擬多帶機(jī)的一步移動(dòng)， S在其帶子上從標(biāo)記左端點(diǎn)的第一個(gè) # 開(kāi)始掃描，一直掃描到標(biāo)記右端點(diǎn)的第 (k+1) 個(gè) #。其目的是確定虛擬讀寫頭下的符號(hào)。然后 S 進(jìn)行第二次掃描，并根據(jù) M 的轉(zhuǎn)移函數(shù)指示的運(yùn)行方式更新其帶子。 3)任何時(shí)候，只要 S 將某個(gè)虛擬讀寫頭向右移動(dòng)到某個(gè)#上面，就意味著 M 已將自己相應(yīng)的讀寫頭移動(dòng)到了其所在的帶子中的空白區(qū)域上，即以前沒(méi)有讀過(guò)的區(qū)域上。因此，S在這個(gè)帶方格上寫下空白符，并將這

22、個(gè)帶方格到最右端的帶方格中的內(nèi)容都向右移動(dòng)一個(gè)格。然后再像以前一樣繼續(xù)模擬。”,42,多帶圖靈機(jī),推論 3.9,一個(gè)語(yǔ)言是圖靈可識(shí)別的，當(dāng)且僅當(dāng)存在多帶圖 靈機(jī)識(shí)別它。,一個(gè)圖靈可識(shí)別語(yǔ)言可由一個(gè)普通的(單帶)圖靈機(jī)識(shí)別，這個(gè)普通圖靈機(jī)是多帶圖靈機(jī)的一個(gè)特例，這就證明了此推論的一個(gè)方向。另一個(gè)方向可由定理3.8得證。,43,非確定型圖靈機(jī),非確定型圖靈機(jī)的有如其名，在計(jì)算的過(guò)程中，機(jī)器可以在多種可能性動(dòng)作中選擇一種繼續(xù)進(jìn)行。它的轉(zhuǎn)移函數(shù)具有如下形式： : Q P(QL, R） 其計(jì)算是一棵樹(shù)，不同分支對(duì)應(yīng)著機(jī)器的不同可能性。,44,非確定型圖靈機(jī),定理 3.10,每個(gè)非確定型圖靈機(jī)都等價(jià)于某一

23、個(gè)確定型圖靈 機(jī)。,能用確定型 TM D 來(lái)模擬非確定型 TM N 的計(jì)算的證明思路是：讓 D 試驗(yàn) N 的非確定性計(jì)算的所有可能分支，若 D能在某個(gè)分支中到達(dá)接受狀態(tài)，則接受；否則 D 的模擬將永不終止。 將 N 在輸入 w 的計(jì)算看作一棵樹(shù)，樹(shù)的每個(gè)分支代表非確定型的分支，結(jié)點(diǎn)是N的一個(gè)格局，根是起始格局。TM D在這個(gè)樹(shù)上搜索接受格局。我們采用“寬度優(yōu)先”策略搜索整棵樹(shù)，這個(gè)策略是：在搜索一個(gè)深度內(nèi)的所有分支之后，再去搜索下一個(gè)深度內(nèi)的所有分支。此方法能保證 D可以訪問(wèn)樹(shù)的所有結(jié)點(diǎn)，直到它遇到接受格局。,45,非確定型圖靈機(jī),用于模擬的確定型 TM D 有 3 個(gè)帶子。根據(jù)定理 3.8，

24、這等價(jià)于只有一個(gè)帶子。機(jī)器 D 將這三個(gè)帶子用于專門用途。第一個(gè)帶子包含輸入串，且不再改變；第二個(gè)帶子存放N的帶子中的內(nèi)容，此內(nèi)容對(duì)應(yīng)N的非確定性計(jì)算的某個(gè)分支；第三個(gè)帶子記錄 D 在 N 的非確定性計(jì)算樹(shù)中的位置。,輸入帶,模擬帶,地址帶,46,非確定型圖靈機(jī),首先考慮第三個(gè)帶子上表示的數(shù)據(jù)。N的每個(gè)格局確定一個(gè)集合，它是由此格局可能轉(zhuǎn)移到的下一個(gè)格局組成，這些下一個(gè)格局是由N的轉(zhuǎn)移函數(shù)指定的。N的非確定性計(jì)算中的每個(gè)結(jié)點(diǎn)最多有b個(gè)子結(jié)點(diǎn)，其中：b是上述集合中最大的集合所含的元素個(gè)數(shù)。對(duì)樹(shù)的每個(gè)結(jié)點(diǎn)，可以給其分配一個(gè)地址，它是字母表 b=1，2，b上的一個(gè)串。 例如，把地址231分配給按以下

25、方式到達(dá)的結(jié)點(diǎn)：從根出發(fā)走到它的第二個(gè)子結(jié)點(diǎn)，再由此走到第三個(gè)子結(jié)點(diǎn)，最后由此走到第一個(gè)子結(jié)點(diǎn)。此串中的數(shù)字告訴我們：在模擬N的非確定計(jì)算的一個(gè)分支時(shí)下一步應(yīng)做什么。如果一個(gè)格局所能有的選擇太少，則一個(gè)符號(hào)可能不對(duì)應(yīng)任何選擇。此種倩況下，地址將無(wú)效，不對(duì)應(yīng)任何結(jié)點(diǎn)。第三個(gè)帶子上包含b上的一個(gè)串，它代表N的計(jì)算樹(shù)中如下分支：起點(diǎn)是根，終點(diǎn)是此串表示的地址所對(duì)應(yīng)的結(jié)點(diǎn)，除非這個(gè)地址是無(wú)效的?？沾菢?shù)根的地址。,47,非確定型圖靈機(jī),D的描述如下： 1)開(kāi)始時(shí)，第一個(gè)帶子包含輸入w，第二和第三個(gè)帶子都是空的。 2)把第一個(gè)帶子復(fù)制到第二個(gè)帶子上。 3)用第二個(gè)帶子去模擬N在輸入w上的非確定性計(jì)算的某

26、個(gè)分支。在N的每一步動(dòng)作之前，查詢第三個(gè)帶子上的下一個(gè)數(shù)字，以決定在N的轉(zhuǎn)移函數(shù)所允許的選擇中作何選擇。如果第三個(gè)帶子上沒(méi)有符號(hào)剩下，或這個(gè)非確定性的選擇是無(wú)效的，則放棄這個(gè)分支，轉(zhuǎn)到第4步。如果遇到拒絕格局也轉(zhuǎn)到第4步。如果遇到接受格局，則接受這個(gè)輸入。 4)在第二個(gè)帶子上，用字典順序下的下一個(gè)串來(lái)替代原有的串。轉(zhuǎn)到第2步，以模擬N的計(jì)算的下一個(gè)分支。,48,非確定型圖靈機(jī),推論 3.11,一個(gè)語(yǔ)言是圖靈可識(shí)別的，當(dāng)且僅當(dāng)存在非確 定型圖靈機(jī)識(shí)別它。,推論 3.12,一個(gè)語(yǔ)言是可判定的，當(dāng)且僅當(dāng)存在非確定型 圖靈機(jī)判定它。,確定型圖靈機(jī)自然是一個(gè)非確定型圖靈機(jī)，此定理的一個(gè)方向由此立刻得證。

27、另個(gè)方向可內(nèi)定理3.10得證。,49,枚舉器,它是圖靈機(jī)的一種變形。粗略地說(shuō)，枚舉器是帶有打印機(jī)的圖靈機(jī)，圖靈機(jī)把打印機(jī)當(dāng)作輸出設(shè)備，從而可以打印串。每當(dāng)圖靈機(jī)想在打印序列中增加一個(gè)串時(shí)，就把此串送到打印機(jī)。 枚舉器以空白輸入帶開(kāi)始運(yùn)行，如果不停機(jī)，它可能會(huì)打印出串的一個(gè)無(wú)限序列。枚舉器 E 所枚舉的語(yǔ)言是最終打印出的串的集合。而且 E 可能以任意順序生成這個(gè)語(yǔ)言中的串，甚至還會(huì)有重復(fù)。,50,枚舉器示意圖,控制器,打印機(jī),aa baba abba,工作帶,51,枚舉器,定理 3.13,一個(gè)語(yǔ)言是圖靈可識(shí)別的，當(dāng)且僅當(dāng)存在枚舉器 枚舉它。,52,枚舉器,首先證明，如果有枚舉器 E 枚舉語(yǔ)言 A

28、，則有 TM M 識(shí)別 A。 TM M如下運(yùn)行： M=“對(duì)于輸入w： 1)運(yùn)行E。每當(dāng)E輸出一個(gè)串時(shí)，將之與w比較。 2)如果w曾經(jīng)在E的輸出中出現(xiàn)過(guò)，則接受?！?顯然，M接受在E的輸出序列中出現(xiàn)過(guò)的那些串。 現(xiàn)在證明另一個(gè)方向。設(shè)s1， s2， s3，是*中的所有串。如果有TM M識(shí)別語(yǔ)言A，為A構(gòu)造枚舉器E如下： E“忽略輸入。 1)對(duì)i1，2，3，重復(fù)下列步驟。 2)對(duì)s1， s2， s3， ，si中的每一個(gè)，M以其作為輸入運(yùn)行i步 3)如果有計(jì)算接受，則打印出相應(yīng)的sj ?！?如果M接受串s，它終將出現(xiàn)在E生成的打印列表中。,53,通用圖靈機(jī),通用 TM (universal Turi

29、ng machine) 實(shí)現(xiàn)對(duì)所有 TM 的模擬。 編碼系統(tǒng) 它可以在實(shí)現(xiàn)對(duì) TM 的表示的同時(shí)，實(shí)現(xiàn)對(duì)該 TM 處理的句子的表示。 用 0 和 1 對(duì)這些除空白符以外的其他的帶符號(hào)進(jìn)行編碼。同時(shí)也可以用 0 和 1 對(duì) TM 的移動(dòng)函數(shù)進(jìn)行編碼。,54,通用圖靈機(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表示。 M 可用 111 code1 11 code2 11 11 coder 1

30、11 codet 是動(dòng)作(qi, Xj)=(qk , Xl, Dm)的形如0i10j10k10l10m的編碼。 TM M 和它的輸入串 w 則可以表示成 111 code1 11 code2 11 11 coder 111w 按照規(guī)范順序分別對(duì)表示 TM 的符號(hào)行和表示輸入的符號(hào)行進(jìn)行排序。,55,通用圖靈機(jī),設(shè)TM M2=( q1, q2, q3, q4, 0, 1, 0, 1, B, , q4 , B ,q3)，其中的定義如下: (q4, 0) = (q4, 0, R) (q4, 1) = (q1, 1, R) (q1, 0) = (q1, 0, R) (q1, 1) = (q2, 1,

31、R) (q2, 0) = (q2, 0, R) (q2, 1) = (q3, 1, R) 編碼為 1110000101000010101100001001010010110101010101101001001001011001010010101100100100010010111 通用 TM 檢查 M 是否接受字符串 001101110 1110000101000010101100001001010010110101010101101001001001011001010010101100100100010010111 001101110,56,主要內(nèi)容,3.1 丘奇圖靈論題 3.1.1 圖靈機(jī)

32、的形式化定義 3.1.2 圖靈機(jī)的例子 3.2 圖靈機(jī)的變形 3.2.1 多帶圖靈機(jī) 3.2.2 非確定型圖靈機(jī) 3.2.3 枚舉器 3.2.4 與其他模型的等價(jià)性 3.3 算法的定義 3.3.1 希爾伯特問(wèn)題 3.3.2 描述圖靈機(jī)的術(shù)語(yǔ),57,算法的定義,非形式地說(shuō)，算法是為實(shí)現(xiàn)某個(gè)任務(wù)而構(gòu)造的簡(jiǎn)單指令集。在日常用語(yǔ)來(lái)說(shuō)，算法有時(shí)稱為過(guò)程或處方。算法在數(shù)學(xué)中也起著重要的作用。古代數(shù)學(xué)文獻(xiàn)中包含了各種各樣任務(wù)的算法描述，如尋找素?cái)?shù)和最大公因子。當(dāng)代數(shù)學(xué)中更是充滿了算法。,58,希爾伯特問(wèn)題,1900年希爾伯特提出了23個(gè)數(shù)學(xué)問(wèn)題。其中的第10個(gè)問(wèn)題是關(guān)于算法的。 通過(guò)有限多次運(yùn)算就可以決定的

33、過(guò)程。 一個(gè)多項(xiàng)式是一些項(xiàng)的和，其中：每個(gè)項(xiàng)都是一個(gè)常數(shù)和一些變?cè)姆e，此常數(shù)叫系數(shù)（coefficient）。 例如，6xxxyzz=6x3yz2是一個(gè)項(xiàng)，其系數(shù)是6； 6x3yz2+3xy2-x3-10 是一個(gè)多項(xiàng)式，它有四個(gè)項(xiàng)和三個(gè)變?cè)獂、y、z 多項(xiàng)式的根（root）是對(duì)它的變?cè)囊粋€(gè)賦值，使此多項(xiàng)式的值為0。 上述多項(xiàng)式的一個(gè)根是x=5、y=3和z=0，這個(gè)根是整數(shù)根（integral root），因?yàn)樗凶冊(cè)急毁x予整數(shù)值。,59,希爾伯特問(wèn)題,丘奇-圖靈論題（Church-Turing thesis） 希爾伯特第10問(wèn)題旨在設(shè)計(jì)一個(gè)算法來(lái)檢測(cè)一個(gè)多項(xiàng)式是否有整數(shù)根。 現(xiàn)在用上述術(shù)語(yǔ)來(lái)重新陳述希爾伯特第10問(wèn)題，設(shè) D= p | p 是有整數(shù)根的多項(xiàng)式