丘奇-圖靈論題.ppt

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

2、：圖靈機(jī), 或 遞歸函數(shù)論,5,引言,在還沒有計算機(jī)的時候， 憑想象力把后來出現(xiàn)的 把計算機(jī)的理論模型建立起來了。 1936年 想得如此周到、嚴(yán)密 好像從高度文明的外星來的文化使者,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 成為理論計算科學(xué)的標(biāo)準(zhǔn)模型standard model,7,引言,圖靈機(jī)（Turing Machine，TM），是計算機(jī)的一種簡單的數(shù)學(xué)模型。 歷史上，馮諾曼計算機(jī)的產(chǎn)生就是由圖靈機(jī)誘發(fā)的。 丘奇圖靈論題：一切合理的計算模型都等同于圖靈機(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 與其他模型的等價性 3.3 算法的定義 3.3.1 希爾伯特問題 3.3.2 描述圖靈機(jī)的術(shù)語,9,3.1 圖靈機(jī)(Turning Mac

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

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

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

7、q0, qaccept, qreject) (1) Q 是狀態(tài)集。 (2) 是輸入字母表，不包括特殊空白符號。 (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ī)的計算方式,開始時，M 以最左邊的 n 個帶方格接收輸入w=w1w2wn *，帶的其余部分保持空白(即填以空白符)，讀寫頭從最左邊的帶方格開始運行，注意 不含空字符，故出現(xiàn)在帶上的第一個空字符表示輸入的結(jié)束。 M 開

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

9、形式化,如果圖靈機(jī)能合法地從格局 C1 一步進(jìn)入 C2，則稱格局 C1產(chǎn)生格局 C2。 設(shè) a, b 和 c 是 中的符號，u 和 v 是 * 中字符串，qi 和 qj是狀態(tài)，則 uaqibv 和 uqjacv 是兩個格局。如果轉(zhuǎn)移函數(shù)滿足 (qi , b) = (qj , c, L)，則說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ī)，可以等價地將狀態(tài)轉(zhuǎn)移函數(shù)簡化 : Q Q L, R 其中 Q 是取消 qaccept 和qreject 的 Q。,25,圖靈機(jī)計算方式的形式化,圖靈機(jī) M 接受輸入 w ，如果存在格局的序列 Cl, C2, , Ck使得： (1) Cl 是 M 在輸入 w 上的起始格局； (2) 每一個Ci 產(chǎn)生 Ci +1； (3) Ck 是接受格局。 M 接受的字符串的集合稱為 M 的語言，或被 M 識別的語言，記為 L(M)。,26,圖靈機(jī)的形式化定義,定義 3.2,如果一個語言能被某一圖靈機(jī)識別，則稱該語言是圖靈可識別的 (Turning recognizable)。 也稱為遞歸可枚舉語言。,輸

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

12、2的方冪的字符串，即 A= | n 0,M2 = “對于輸入字符串w： 1) 從左往右掃描整個帶子，隔一個字符消去一個0。 2) 如果在第1步之后，帶子上只剩下唯一的一個0，則接受。 3) 如果在第1步之后，帶子上包含不止一個0，并且0的個數(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 步，消去了一半個數(shù)的 0。由于在第 1 步中，機(jī)器掃描了整個帶子

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

14、Q, , , , q1, qaccept, qreject)， 它的判定語言是 B = w#w | w 0, 1* 。,Q = q1, q2, , q8 , qaccept, qreject ， = 0, 1, # 且 = 0, 1, #, x, 。 用狀態(tà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 實現(xiàn)

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

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

17、描下一個 #，并在其頂上做第二個記號。如果在遇到空白符之前沒有遇到 #，則帶上只有 x1 ，因此接受。 3) 通過來回移動，比較做了記號的 # 的右邊的兩個字符串，如果它們相等，則拒絕。 4) 將兩個記號中右邊的那個向右移到下一個 # 上。如果在碰到空白符之前沒有遇到 #，則將左邊的記號向右移到下一個 # 上，并且將右邊記號移到后面的 # 上。如果這時右邊記號還找不到 #，則所有的字符串都已經(jīng)比較過了，因而接受。 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 與其他模型的等價性 3.3 算法的定義 3.3.1 希爾伯特問題 3.3.2 描述圖靈機(jī)的術(shù)語,37,圖靈機(jī)的變形,從不同的方面對 TM 進(jìn)行擴(kuò)充。 雙向無窮帶 TM 允許 TM 的輸入帶是無窮的。 多帶 TM 允許 TM 有多于一條的輸入帶。此時每條帶上將有一個讀頭。 不確定的 TM 允許 TM 在某一狀態(tài)下根據(jù)讀入的符號選擇地進(jìn)行某一個動作：進(jìn)入某個狀態(tài)，在讀頭的當(dāng)前位置印刷某個符號，將讀頭移向某個方向。 多維 TM 相當(dāng)于在雙向 TM 的基礎(chǔ)上進(jìn)一步擴(kuò)充，允許TM 的“輸入帶”向更多的方向延伸。 枚舉器允許圖靈機(jī)帶有打印機(jī)。 它們與基

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

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

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

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

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

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

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

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

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

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

29、ng machine) 實現(xiàn)對所有 TM 的模擬。 編碼系統(tǒng) 它可以在實現(xiàn)對 TM 的表示的同時，實現(xiàn)對該 TM 處理的句子的表示。 用 0 和 1 對這些除空白符以外的其他的帶符號進(jìn)行編碼。同時也可以用 0 和 1 對 TM 的移動函數(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 是動作(qi, Xj)=(qk , Xl, Dm)的形如0i10j10k10l10m的編碼。 TM M 和它的輸入串 w 則可以表示成 111 code1 11 code2 11 11 coder 111w 按照規(guī)范順序分別對表示 TM 的符號行和表示輸入的符號行進(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 與其他模型的等價性 3.3 算法的定義 3.3.1 希爾伯特問題 3.3.2 描述圖靈機(jī)的術(shù)語,57,算法的定義,非形式地說，算法是為實現(xiàn)某個任務(wù)而構(gòu)造的簡單指令集。在日常用語來說，算法有時稱為過程或處方。算法在數(shù)學(xué)中也起著重要的作用。古代數(shù)學(xué)文獻(xiàn)中包含了各種各樣任務(wù)的算法描述，如尋找素數(shù)和最大公因子。當(dāng)代數(shù)學(xué)中更是充滿了算法。,58,希爾伯特問題,1900年希爾伯特提出了23個數(shù)學(xué)問題。其中的第10個問題是關(guān)于算法的。 通過有限多次運算就可以決定的

33、過程。 一個多項式是一些項的和，其中：每個項都是一個常數(shù)和一些變元的積，此常數(shù)叫系數(shù)（coefficient）。 例如，6xxxyzz=6x3yz2是一個項，其系數(shù)是6； 6x3yz2+3xy2-x3-10 是一個多項式，它有四個項和三個變元x、y、z 多項式的根（root）是對它的變元的一個賦值，使此多項式的值為0。 上述多項式的一個根是x=5、y=3和z=0，這個根是整數(shù)根（integral root），因為所有變元都被賦予整數(shù)值。,59,希爾伯特問題,丘奇-圖靈論題（Church-Turing thesis） 希爾伯特第10問題旨在設(shè)計一個算法來檢測一個多項式是否有整數(shù)根。 現(xiàn)在用上述術(shù)語來重新陳述希爾伯特第10問題，設(shè) D= p | p 是有整數(shù)根的多項式