【正文】 注意力集中在后面將要討論的 復(fù)雜度， P 、 NP問題，不必拘泥與這些技術(shù)細(xì)節(jié) Univ. 可計(jì)算理論 2022/8/14 67/88 Outline Proof Thm. ep137, cp95 模擬結(jié)構(gòu) 造單帶機(jī)模擬多帶機(jī) （多帶機(jī)模擬單帶機(jī)不需證明） 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道上當(dāng)前字符 ?第 1道 第 k道格局 Univ. 可計(jì)算理論 2022/8/14 68/88 Outline Proof Thm. ep137, cp95 模擬結(jié)構(gòu) 造單帶機(jī)模擬多帶機(jī) （多帶機(jī)模擬單帶機(jī)不需證明） 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道上當(dāng)前字符 ?第 1道 第 k道格局 Univ. 可計(jì)算理論 2022/8/14 69/88 Proof Thm. (cont.) ep137, cp95 模擬動(dòng)作 On input w=w1…w n, the TM M? does the following: ? Prepare initial string: w1…w n_? __ ? ? 多帶復(fù)制到單帶 ? Read the underlined input letters ? ?k 各帶當(dāng)前字 ? Simulate M by updating the input and the underlining of the headpositions. ? 通過下標(biāo)映射模擬動(dòng)作 ? 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. 可計(jì)算理論 2022/8/14 70/88 Proof Thm. (cont.) ep137, cp95 模擬動(dòng)作 On input w=w1…w n, the TM M? does the following: ? Prepare initial string: w1…w n_? __ ? ? 多帶復(fù)制到單帶 ? Read the underlined input letters ? ?k 各帶當(dāng)前字 ? Simulate M by updating the input and the underlining of the headpositions. ? 通過下標(biāo)映射模擬動(dòng)作 ? 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. 可計(jì)算理論 2022/8/14 71/88 Proof Thm. (cont.) ep137, cp95 模擬動(dòng)作 On input w=w1…w n, the TM M? does the following: ? Prepare initial string: w1…w n_? __ ? ? 多帶復(fù)制到單帶 ? Read the underlined input letters ? ?k 各帶當(dāng)前字 ? Simulate M by updating the input and the underlining of the headpositions. ? 通過下標(biāo)映射模擬動(dòng)作 ? 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. 可計(jì)算理論 2022/8/14 72/88 Nondeterministic TMs ep138 cp94 非確定圖靈機(jī) 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. 可計(jì)算理論 2022/8/14 73/88 Nondeterministic TMs ep138 cp94 非確定圖靈機(jī) 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. 可計(jì)算理論 2022/8/14 74/88 Nondeterministic TMs ep138 cp94 非確定圖靈機(jī) 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。 注意力集中在后面將要討論的 復(fù)雜度， P 、 NP問題，不必拘泥與這些技術(shù)細(xì)節(jié) Univ. 可計(jì)算理論 2022/8/14 66/88 Outline Proof Thm. ep137, cp95 另一種比喻 ：先寫一個(gè)有 4個(gè)數(shù)組的 C程序 ,然后寫一個(gè)只有一個(gè)數(shù)組的程序區(qū)模擬上述程序， 直觀上是容易接受的，因?yàn)? 用下標(biāo)映射實(shí)現(xiàn)模擬的難度不大。 a e i . . 男聲 b f j . . 女生 c g k . . 鼓點(diǎn) d h l . . 配樂 Univ. 可計(jì)算理論 2022/8/14 65/88 Outline Proof Thm. ep137, cp95 另一種比喻 ：先寫一個(gè)有 4個(gè)數(shù)組的 C程序 ,然后寫一個(gè)只有一個(gè)數(shù)組的程序去模擬上述程序， 直觀上是容易接受的，因?yàn)? 用下標(biāo)映射實(shí)現(xiàn)模擬的難度不大。 Standard tools: Expanding the alphabet with separator “”, and underlined symbols 0, a, to indicate ?activity?. Typical: ? = { 0,1,_,0,1 } Univ. 可計(jì)算理論 2022/8/14 57/88 When Describing TM ep133 略 It is assumed that you are familiar with TMs and with programming puters. Clarity above all: high level description of TMs is allowed but should not be used as a trick to hide the important details of the program. Standard tools: Expanding the alphabet with separator “”, and underlined symbols 0, a, to indicate ?activity?. Typical: ? = { 0,1,_,0,1 } Univ. 可計(jì)算理論 2022/8/14 58/88 Multitape Turing Machines 多帶圖靈機(jī) ep136, cp93 增加數(shù)組資源，期望編程簡單 A ktape Turing machine M has k different tapes and read/write heads. It is thus 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} ? ?k ? Q ? ?k ? {L,R}k ? 轉(zhuǎn) 寫 移 ?根據(jù) K條帶上的存儲(chǔ)數(shù)據(jù)現(xiàn)狀決定 寫，移，轉(zhuǎn) 動(dòng)作 Univ. 可計(jì)算理論 2022/8/14 59/88 Multitape Turing Machines 多帶圖靈機(jī) ep136, cp93, 增加數(shù)組資源，期望編程簡單 A ktape Turing machine M has k different tapes and read/write heads. It is thus 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