【文章內(nèi)容簡介】 開始、接受和拒絕狀態(tài)分別是 q1, qaccept, qreject 31 圖靈機(jī)舉例 例 下面給出圖靈機(jī) M1 形式化描述 M1= (Q, ?, ?, ?, q1, qaccept, qreject)， 它的判定語言是 B = { ww | 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 x?R □?R 0,1?R ?R x?R 0,1,x?L 0,1?L ?L x?R ?R 0,1?R x?R 第一步由 q1 到 q7 實現(xiàn)，第二步由其余狀態(tài)實現(xiàn) 33 圖靈機(jī)舉例 例 圖靈機(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 是否都已被消去。如果是，則接受，否則拒絕。” 34 圖靈機(jī)舉例 例 圖靈機(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) 向右掃描下一個 ，并在其頂上做第二個記號。如果在遇到空白符之前沒有遇到 ，則帶上只有 x1 ，因此接受。 3) 通過來回移動，比較做了記號的 的右邊的兩個字符串，如果它們相等，則拒絕。 4) 將兩個記號中右邊的那個向右移到下一個 上。如果在碰到空白符之前沒有遇到 ，則將左邊的記號向右移到下一個 上，并且將右邊記號移到后面的 上。如果這時右邊記號還找不到 ，則所有的字符串都已經(jīng)比較過了，因而接受。 5) 轉(zhuǎn)到第 3 步繼續(xù)執(zhí)行。” 36 主要內(nèi)容 丘奇 —圖靈論題 圖靈機(jī)的形式化定義 圖靈機(jī)的例子 圖靈機(jī)的變形 多帶圖靈機(jī) 非確定型圖靈機(jī) 枚舉器 與其他模型的等價性 算法的定義 希爾伯特問題 描述圖靈機(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ī) 。 ? …… ?它們與基本的 TM 等價。 ?在形式變化中 保持不變的性質(zhì) 稱為 穩(wěn)健性 。 38 多帶圖靈機(jī) ?多帶圖靈機(jī) (multitape Turing Machine) 很像普通圖靈機(jī)，只是有多個帶子， 每個帶子都有自己的讀寫頭 ，用于讀和寫。開始時，輸入出現(xiàn)在第一個帶子上，其它的帶子都是空白 。轉(zhuǎn)移函數(shù)改為允許多個帶子同時進(jìn)行讀、寫和移動讀寫頭，其形式為： ?： Q ?k ? Q ?k {L, R, S}k 此處 k 是帶子的個數(shù)。表達(dá)式 ?( qi , a1 , a2 , …, ak ) = ( qj, b1, b2, …, bk , L, R, …, L) 指的是：若機(jī)器處于狀態(tài) qi ，讀寫頭 1 到 k 所讀的符號分別是 a1 到 ak ， 則機(jī)器轉(zhuǎn)移到狀態(tài) qj，各讀寫頭分別 寫下符號 b1 到 bk，且按此式所指示的那樣移動每個讀寫頭。 39 多帶圖靈機(jī) 定理 每個多帶圖靈機(jī)等價于某一個單帶圖靈機(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ī) 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 = “對于輸入 w=w1… wn： 1) S 在白己的帶子上放入 w1w2… wn□ □ … （上邊沒加點） 此格式表示了 M 的全部 k 個帶子的內(nèi)容。 2)為了模擬多帶機(jī)的一步移動， S在其帶子上從標(biāo)記左端點的第一個 開始掃描，一直掃描到標(biāo)記右端點的第 (k+1) 個 。其目的是確定虛擬讀寫頭下的符號。然后 S 進(jìn)行第二次掃描，并根據(jù) M 的轉(zhuǎn)移函數(shù)指示的運行方式更新其帶子。