【正文】 分別表示 R,L。 δ(qi, Xj)=(qk , Xl, Dm) 可以用 0i10j10k10l10m表示。 ? M 可用 111 code1 11 code2 11 …… 11 code r 111 ? codet 是動作 δ(qi, Xj)=(qk , Xl, Dm)的形如 0i10j10k10l10m的編碼。 ? TM M 和它的輸入串 w 則可以表示成 111 code1 11 code2 11 …… 11 code r 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, R) δ(q2, 0) = (q2, 0, R) δ(q2, 1) = (q3, 1, R) ?編碼為 1110000101000010101100001001010010110101010101101001001001011001010010101100100100010010111 ?通用 TM 檢查 M 是否接受字符串 001101110 1110000101000010101100001001010010110101010101101001001001011001010010101100100100010010111 001101110 56 主要內(nèi)容 丘奇 —圖靈論題 圖靈機(jī)的形式化定義 圖靈機(jī)的例子 圖靈機(jī)的變形 多帶圖靈機(jī) 非確定型圖靈機(jī) 枚舉器 與其他模型的等價性 算法的定義 希爾伯特問題 描述圖靈機(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)于算法的。 通過有限多次運算就可以決定的過程。 ?一個 多項式 是一些項的和，其中：每個項都是一個常數(shù)和一些變元的積，此常數(shù)叫 系數(shù) （ coefficient）。 ?例如， 6xxxyzz=6x3yz2是一個項，其系數(shù)是 6； 6x3yz2+3xy2x310 是一個多項式，它有四個項和三個變元x、 y、 z ?多項式的 根 （ root）是對它的變元的一個賦值，使此多項式的值為 0。 ?上述多項式的一個根是 x= y=3和 z=0，這個根是 整數(shù)根（ integral root），因為所有變元都被賦予整數(shù)值。 59 希爾伯特問題 ?丘奇 圖靈論題（ ChurchTuring thesis） ?希爾伯特第 10問題旨在設(shè)計一個算法來檢測一個多項式是否有整數(shù)根。 ? 現(xiàn)在用上述術(shù)語來重新陳述希爾伯特第 10問題，設(shè) D={ p | p 是有整數(shù)根的多項式 } 本質(zhì)上，希爾伯特第 10 個問題是問； 集合 D 是不是可判定的 ? 答案是否定的。 算法的直覺概念 等于 圖靈機(jī)算法 60 希爾伯特問題 ?考慮只有一個變元的多項式，如 4x32x2+x7。設(shè) D1 ={ p | p 是有整數(shù)根 x的多項式 } ?下面是識別 D1 的圖靈機(jī) M1： M1 =“輸入是關(guān)于變元 x 的一個多項式 p 當(dāng) x 相繼被設(shè)置為值 0, 1, 1, 2, 2, 3, 1, … 時，求 p 的值，一旦求得 0 值，就接受。” 如果 p 有整數(shù)根， M1 最終將找到它，從而接受； 如果 p 沒有整數(shù)根，則 M1 將永遠(yuǎn)運行下去。 ?對于多變元的情形，可以設(shè)計一個類似的圖靈機(jī) M 來識別D，只是 M 要檢查多個變元所有可能取的整數(shù)值。 61 描述圖靈機(jī)的術(shù)語 ?描述的詳細(xì)程度有三種： 形式化描述 實現(xiàn)描述 高水平描述 62 圖靈機(jī)的格式和記號 ?圖靈機(jī)的輸入總是一個串。如果想以一個對象而不是字符串的作為輸入，必須先將那個對象字符串化。 ?對象 O 的編碼成字符串的記號是 O。如果有多個對象 O1, O2,…, Ok，它們的編碼是一個串，記為 O1, O2,…, Ok 。 ?描述圖靈機(jī)算法的格式是帶引號的文字段，且 排成鋸齒形狀 。將算法分成幾個步驟，每個步驟可能包括圖靈機(jī)計算的許多步，用更深的縮進(jìn)方式來指示算法的分塊結(jié)構(gòu)。 算法的第一行描述機(jī)器的輸入 。如果輸入描述僅僅被寫成 w，則這個串就被當(dāng)作輸入，如果輸入描述是一個對象的編碼 A ，則暗示圖靈機(jī)需要首先檢查此輸入是否確實是所要的對象的編碼，如果不是，則拒絕它。 63 描述圖靈機(jī)的術(shù)語 例 設(shè) A 是由表示連通無向圖的串構(gòu)成的語言。回憶一下，如果一個圖從任意頂點出發(fā)，都可以沿著邊走到其它所有頂點，則稱這個圖是 連通的 。記 A 為 A = { G | G 是連通無向圖 } 下面是判定 A 的 TM M 的一個高層次描述： M=“輸入是圖 G 的編碼 G ： 1)選擇 G 的第一個頂點，并標(biāo)記之。 2)重復(fù)下列步驟，直到?jīng)]有新的頂點可作標(biāo)記。 3)對于 G 的每一個頂點，如果能通過一條邊將其連到另一 個已被標(biāo)記的頂點，則標(biāo)記該頂點。 4)掃描 G 的所有頂點，確定它們是否都已做了標(biāo)記，如果 是，則接受，否則拒絕。 64 描述圖靈機(jī)的術(shù)語 1 2 3 4 G= G=(1,2,3,4,)((1,2),(2,3),(3,1),(1,4)) 65 本章小結(jié) ?丘奇 —圖靈論題 圖靈機(jī)的形式化定義、構(gòu)造方法 ?圖靈機(jī)的變形 多帶圖靈機(jī)、 非確定型圖靈機(jī)、枚舉器、通用圖靈機(jī) ?算法的定義 熟悉算法的描述方式、描述圖靈機(jī)的術(shù)語 66 作業(yè) ? , , , , , ,