【正文】 llows: A language L is TMrecognizable if and only if some multitape TM recognizes L. 以后可用 多帶機 作題，簡單多了 Univ. 可計算理論 2022/8/14 62/88 ktape TMs versus 1tape TMs ep137, cp93 Theorem : For every multitape TM M, there is a singletape TM M? such that L(M)=L(M?). Or, for every multitape TM M, there is an equivalent singletape TM M?. 多 帶機 與單帶機等價 增加存儲和數(shù)組 (多帶 )只提速和簡化， 無本質(zhì)改變 Proving and understanding these kinds of robustness results, is essential for appreciating the power of the Turing machine model. 稱為穩(wěn)健性 From this theorem Corollary follows: A language L is TMrecognizable if and only if some multitape TM recognizes L. 以后可用 多帶機 作題，簡單多了 Univ. 可計算理論 2022/8/14 63/88 ktape TMs versus 1tape TMs ep137, cp88 Theorem : For every multitape TM M, there is a singletape TM M? such that L(M)=L(M?). Or, for every multitape TM M, there is an equivalent singletape TM M?. 多 帶機 與單帶機等價 增加存儲和數(shù)組 (多帶 )只提速和簡化， 無本質(zhì)改變 Proving and understanding these kinds of robustness results, is essential for appreciating the power of the Turing machine model. 稱為穩(wěn)健性 From this theorem Corollary follows: A language L is TMrecognizable if and only if some multitape TM recognizes L. 以后可用 多帶機 作題，簡單多了 Univ. 可計算理論 2022/8/14 64/88 Outline Proof Thm. ep137, cp95 基本思想：用 單磁頭 讀 4聲道錄音磁帶 ,讀出后復制在一條帶上，通過 mod(4),和數(shù)組下標映射，可以標識原產(chǎn)地，但能 算出 4帶機的任務。內(nèi)存少一些，程序復雜一點， 慢一點。 a e i . . 男聲 b f j . . 女生 c g k . . 鼓點 d h l . . 配樂 Univ. 可計算理論 2022/8/14 65/88 Outline Proof Thm. ep137, cp95 另一種比喻 ：先寫一個有 4個數(shù)組的 C程序 ,然后寫一個只有一個數(shù)組的程序去模擬上述程序， 直觀上是容易接受的，因為 用下標映射實現(xiàn)模擬的難度不大。 注意，現(xiàn)在下標需要順序掃描，以后可證明可按下標隨機存取圖靈機（隨機圖靈機） 寫論文時從來不限制只能用 低級圖靈機 證明問題，可以用最先進的工具。 注意力集中在后面將要討論的 復雜度， P 、 NP問題，不必拘泥與這些技術(shù)細節(jié) Univ. 可計算理論 2022/8/14 66/88 Outline Proof Thm. ep137, cp95 另一種比喻 ：先寫一個有 4個數(shù)組的 C程序 ,然后寫一個只有一個數(shù)組的程序區(qū)模擬上述程序， 直觀上是容易接受的，因為 用下標映射實現(xiàn)模擬的難度不大。 注意，現(xiàn)在下標需要順序掃描，以后可證明可按下標隨機存取圖靈機（隨機圖靈機） 寫論文時從來不限制只能用 低級圖靈機 證明問題，可以用最先進的工具。 注意力集中在后面將要討論的 復雜度， P 、 NP問題，不必拘泥與這些技術(shù)細節(jié) Univ. 可計算理論 2022/8/14 67/88 Outline Proof Thm. ep137, cp95 模擬結(jié)構(gòu) 造單帶機模擬多帶機 （多帶機模擬單帶機不需證明） Let M=(Q,?,?,?,q0,qaccept,qreject) be a ktape TM. Construct 1tape M? with expanded ?? = ?? ??{} Represent Mconfiguration u1qja1v1, u2qja2v2, …, ukqjakvk by M? configuration, qj u1a1v1 u2a2v2 … u kakvk 分帶符 , K道上當前字符 ?第 1道 第 k道格局 Univ. 可計算理論 2022/8/14 68/88 Outline Proof Thm. ep137, cp95 模擬結(jié)構(gòu) 造單帶機模擬多帶機 （多帶機模擬單帶機不需證明） Let M=(Q,?,?,?,q0,qaccept,qreject) be a ktape TM. Construct 1tape M? with expanded ?? = ?? ??{} Represent Mconfiguration u1qja1v1, u2qja2v2, …, ukqjakvk by M? configuration, qj u1a1v1 u2a2v2 … u kakvk 分帶符 , K道上當前字符 ?第 1道 第 k道格局 Univ. 可計算理論 2022/8/14 69/88 Proof Thm. (cont.) ep137, cp95 模擬動作 On input w=w1…w n, the TM M? does the following: ? Prepare initial string: w1…w n_? __ ? ? 多帶復制到單帶 ? Read the underlined input letters ? ?k 各帶當前字 ? Simulate M by updating the input and the underlining of the headpositions. ? 通過下標映射模擬動作 ? Repeat 23 until M has reached a halting state ? Halt accordingly. PS: If the update requires overwriting a symbol, then shift the part ? _ one position to the right. Univ. 可計算理論 2022/8/14 70/88 Proof Thm. (cont.) ep137, cp95 模擬動作 On input w=w1…w n, the TM M? does the following: ? Prepare initial string: w1…w n_? __ ? ? 多帶復制到單帶 ? Read the underlined input letters ? ?k 各帶當前字 ? Simulate M by updating the input and the underlining of the headpositions. ? 通過下標映射模擬動作 ? Repeat 23 until M has reached a halting state ? Halt accordingly. PS: If the update requires overwriting a symbol, then shift the part ? _ one position to the right. Univ. 可計算理論 2022/8/14 71/88 Proof Thm. (cont.) ep137, cp95 模擬動作 On input w=w1…w n, the TM M? does the following: ? Prepare initial string: w1…w n_? __ ? ? 多帶復制到單帶 ? Read the underlined input letters ? ?k 各帶當前字 ? Simulate M by updating the input and the underlining of the headpositions. ? 通過下標映射模擬動作 ? Repeat 23 until M has reached a halting state ? Halt accordingly. PS: If the update requires overwriting a symbol, then shift the part ? _ one position to the right. Univ. 可計算理論 2022/8/14 72/88 Nondeterministic TMs ep138 cp94 非確定圖靈機 A nondeterministic Turing machine M can have several options at every step. It is defined by the 7tuple (Q,?,?,?,q0,qaccept,qreject), with ? Q finite set of states ? ? finite input alphabet (without “_”) ? ? finite tape alphabet with { _ } ? ? ? ? ? q0 start state ? Q ? qaccept accept state ? Q ? qreject reject state ? Q ? ? the transition function ?: Q\{qaccept,qreject} ? ? ? P (Q ? ? ? {L,R}) Univ. 可計算理論 2022/8/14 73/88 Nondeterministic TMs ep138 cp94 非確定圖靈機 A nondeterministic Turing machine M can have several options at every step. It is defined by the 7tuple (Q,?,?,?,q0,qaccept,qreject), with ? Q finite set of states ? ? finite input alphabet (without “_”) ? ? finite tape alphabet with { _ } ? ? ? ? ? q0 start state ? Q ? qaccept accept state ? Q ? qreject reject state ? Q ? ? the transition function ?: Q\{qaccept,qreject} ? ? ? P (Q ? ? ? {L,R}) Univ. 可計算理論 2022/8/14 74/88 Nondeterministic TMs ep138 cp94 非確定圖靈機 A nondeterministic Turing machine M can have several options at every step. It is defined by the 7tuple (Q,?,?,?,q0,qaccept,qreject), with ? Q finite set of states ? ? finite input alphabet (without “_”) ? ? finite tape alphabet with { _ } ? ? ? ? ? q0 start state