【正文】 個(gè)串時(shí)，就把此串送到打印機(jī)。 4)在第二個(gè)帶子上，用字典順序下的下一個(gè)串來(lái)替代原有的串?？沾菢?shù)根的地址 。 N的每個(gè)格局確定一個(gè)集合，它是由此格局可能轉(zhuǎn)移到的下一個(gè)格局組成，這些下一個(gè)格局是由 N的轉(zhuǎn)移函數(shù)指定的。 TM D在這個(gè)樹(shù)上搜索接受格局?！? 42 多帶圖靈機(jī) 推論 一個(gè)語(yǔ)言是圖靈可識(shí)別的，當(dāng)且僅當(dāng)存在多帶圖 靈機(jī)識(shí)別它。像以前一樣，加點(diǎn)的帶符號(hào)應(yīng)是已經(jīng)加進(jìn)帶字母表的新符號(hào)。轉(zhuǎn)移函數(shù)改為允許多個(gè)帶子同時(shí)進(jìn)行讀、寫和移動(dòng)讀寫頭，其形式為： ?： Q ?k ? Q ?k {L, R, S}k 此處 k 是帶子的個(gè)數(shù)。此時(shí)每條帶上將有一個(gè)讀頭。 3) 通過(guò)來(lái)回移動(dòng)，比較做了記號(hào)的 的右邊的兩個(gè)字符串，如果它們相等，則拒絕。 此語(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)行比較，依此類推。 3) 消去一個(gè) a，并向右掃描直到 b 出現(xiàn)。由于在第 1 步中，機(jī)器掃描了整個(gè)帶子，故它能夠知道它看到的 0 的個(gè)數(shù)是奇數(shù)還是偶數(shù)，如果是大于 1 的奇數(shù)，則輸入中所含的 0 的個(gè)數(shù)不可能是 2 的方冪，此時(shí)機(jī)器就拒絕。 也稱為 遞歸語(yǔ)言 。 是 取消 qaccept 和 qreject 的 Q。 ?對(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)都是空白符。 (4) ? : Q ?? Q ? { L, R }是轉(zhuǎn)移函數(shù)。 (4)圖靈機(jī) 進(jìn)入拒絕和接受狀體將立即停機(jī) 。 ?丘奇 —圖靈論題：一切合理的計(jì)算模型都等同于圖靈機(jī) . 8 主要內(nèi)容 丘奇 —圖靈論題 圖靈機(jī)的形式化定義 圖靈機(jī)的例子 圖靈機(jī)的變形 多帶圖靈機(jī) 非確定型圖靈機(jī) 枚舉器 與其他模型的等價(jià)性 算法的定義 希爾伯特問(wèn)題 描述圖靈機(jī)的術(shù)語(yǔ) 9 圖靈機(jī) (Turning Machine) 非形式化描述 根據(jù)當(dāng)前狀態(tài)和字符 xi ，決定 寫 移 轉(zhuǎn) 三動(dòng)作 寫 letter, 有存儲(chǔ)器 左或右移動(dòng) 轉(zhuǎn)移狀態(tài) 可以作循環(huán)語(yǔ)句 磁帶相當(dāng)于數(shù)組，可讀寫。這是增加的重要資源 internal state set Q R L ?__10_1101每一步，讀寫頭在單向無(wú)窮帶上左右移動(dòng)并讀寫。 13 圖靈機(jī) ?考慮圖靈機(jī) M1，它檢查語(yǔ)言 B = { ww | w∈ {0,1}* } 的成員關(guān)系。 (5) q0 是起始狀態(tài)。 ? 例如， 1011q701111 1 0 1 1 0 1 1 1 1 ? ? ? q7 24 圖靈機(jī)計(jì)算方式的形式化 ?如果圖靈機(jī)能合法地從格局 C1 一步進(jìn)入 C2，則稱格局 C1產(chǎn)生 格局 C2。 25 圖靈機(jī)計(jì)算方式的形式化 ?圖靈機(jī) M 接受輸入 w ，如果存在格局的序列 Cl, C2, …, Ck使得： (1) Cl 是 M 在輸入 w 上的起始格局； (2) 每一個(gè) Ci 產(chǎn)生 Ci +1； (3) Ck 是接受格局。 可識(shí)別與可判定？ —— 接受該語(yǔ)言； —— 可以不接受該語(yǔ)言。但是，如果看到的 0 的個(gè)數(shù)是 1，則輸入中所含的 0 的個(gè)數(shù)肯定是 2 的方冪，此時(shí)機(jī)器就接受。在 b 與 c 之間來(lái)回移動(dòng)，成對(duì)地消去 b 和 c，直到把所有的 b 都消去。 M4 的非形式描述如下。 4) 將兩個(gè)記號(hào)中右邊的那個(gè)向右移到下一個(gè) 上。 ? 不確定的 TM 允許 TM 在某一狀態(tài)下根據(jù)讀入的符號(hào) 選擇地進(jìn)行某一個(gè)動(dòng)作 ：進(jìn)入某個(gè)狀態(tài)，在讀頭的當(dāng)前位置印刷某個(gè)符號(hào)，將讀頭移向某個(gè)方向。表達(dá)式 ?( qi , a1 , a2 , …, ak ) = ( qj, b1, b2, …, bk , L, R, …, L) 指的是：若機(jī)器處于狀態(tài) qi ，讀寫頭 1 到 k 所讀的符號(hào)分別是 a1 到 ak ， 則機(jī)器轉(zhuǎn)移到狀態(tài) qj，各讀寫頭分別 寫下符號(hào) b1 到 bk，且按此式所指示的那樣移動(dòng)每個(gè)讀寫頭。 40 多帶圖靈機(jī) 0 1 0 1 0 □ … M a a a □ … b a □ … 0 1 0 1 0 a a a b a □ … S 41 多帶圖靈機(jī) ? S = “對(duì)于輸入 w=w1… wn： 1) S 在白己的帶子上放入 w1w2… wn□ □ … （上邊沒(méi)加點(diǎn)） 此格式表示了 M 的全部 k 個(gè)帶子的內(nèi)容。 一個(gè)圖靈可識(shí)別語(yǔ)言可由一個(gè)普通的 (單帶 )圖靈機(jī)識(shí)別，這個(gè)普通圖靈機(jī)是多帶圖靈機(jī)的一個(gè)特例，這就證明了此推論的一個(gè)方向。我們采用“寬度優(yōu)先”策略搜索整棵樹(shù)，這個(gè)策略是： 在搜索一個(gè)深度內(nèi)的所有分支之后，再去搜索下一個(gè)深度內(nèi)的所有分支 。 N的非確定性計(jì)算中的每個(gè)結(jié)點(diǎn)最多有 b個(gè)子結(jié)點(diǎn)，其中：b是上述集合中最大的集合所含的元素個(gè)數(shù)。 47 非確定型圖靈機(jī) ? D的描述如下： 1)開(kāi)始時(shí)，第一個(gè)帶子包含輸入 w，第二和第三個(gè)帶子都是空的。轉(zhuǎn)到第 2步，以模擬 N的計(jì)算的下一個(gè)分支。 ?枚舉器以空白輸入帶開(kāi)始運(yùn)行， 如果不停機(jī)，它可能會(huì)打印出串的一個(gè)無(wú)限序列。” 顯然， M接受在 E的輸出序列中出現(xiàn)過(guò)的那些串。 ?編碼系統(tǒng) ? 它可以在實(shí)現(xiàn)對(duì) TM 的表示的同時(shí)，實(shí)現(xiàn)對(duì)該 TM 處理的句子的表示。在日常用語(yǔ)來(lái)說(shuō)，算法有時(shí)稱為過(guò)程或處方。 ?例如， 6 59 希爾伯特問(wèn)題 ?丘奇 圖靈論題（ ChurchTuring thesis） ?希爾伯特第 10問(wèn)題旨在設(shè)計(jì)一個(gè)算法來(lái)檢測(cè)一個(gè)多項(xiàng)式是否有整數(shù)根。 ?對(duì)象 O 的編碼成字符串的記號(hào)是 O。記 A 為 A = { G | G 是連通無(wú)向圖 } 下面是判定 A 的 TM M 的一個(gè)高層次描述： M=“輸入是圖 G 的編碼 G ： 1)選擇 G 的第一個(gè)頂點(diǎn)，并標(biāo)記之。 3)對(duì)于 G 的每一