【文章內(nèi)容簡介】 that the configuration “uaqibv” yields the configuration “uacqjb” if and only if: ?(qi,b) = (qj,c,R). 格局產(chǎn)生 即 格局 按機(jī)演化 翻譯成 格局演進(jìn) 似更恰當(dāng) Similarly, if ?(qi,b) = (qj,c,L) // 把當(dāng)前的 b改為 c 且左移 then “uaqibv” yields “uqjacb” (At the leftmost side of the tape different.) Univ. 可計(jì)算理論 2022/8/14 37/88 An Elementary TM Step ep129 cp89 Let u,v? ?* 。 a,b,c? ? 。 qi,qj?Q, and M a TM with transition function ?. 格局 C1產(chǎn)生格局 C2 We say that the configuration “uaqibv” yields the configuration “uacqjv” if and only if: ?(qi,b) = (qj,c,R). 格局產(chǎn)生 即 格局 按機(jī)演化 翻譯成 格局演進(jìn) 似更恰當(dāng) Similarly, if ?(qi,b) = (qj,c,L) // 把當(dāng)前的 b改為 c 且左移 then “uaqibv” yields “uqjacv” (At the leftmost side of the tape different.) Univ. 可計(jì)算理論 2022/8/14 38/88 Terminology 格局 starting configuration on input w: “q0w” 初始格局 accepting configuration: “uqacceptv” 接受格局 返回 true rejecting configuration: “uqrejectv” 拒絕格局 返回 false The accepting and rejecting configurations are the halting configurations. Univ. 可計(jì)算理論 2022/8/14 39/88 Terminology 格局 starting configuration on input w: “q0w” 初始格局 accepting configuration: “uqacceptv” 接受格局 返回 true rejecting configuration: “uqrejectv” 拒絕格局 返回 false The accepting and rejecting configurations are the halting configurations. Univ. 可計(jì)算理論 2022/8/14 40/88 用格局概念描述 Accepting ep129 ,cp89 A Turing machine M accepts input w??* if and only if there is a finite sequence of configurations C1,C2,…,C k with ? C1 the starting configuration “q0w” ? for all i=1,…,k –1 Ci yields Ci+1 (following M?s ?) ? Ck is an accepting configuration “uqacceptv” The language that consists of all inputs that are accepted by M is denoted by L(M). 比喻： bool M(w) 最后返回 true Univ. 可計(jì)算理論 2022/8/14 41/88 用格局概念描述 Accepting ep129 ,cp89 A Turing machine M accepts input w??* if and only if there is a finite sequence of configurations C1,C2,…,C k with ? C1 the starting configuration “q0w” ? for all i=1,…,k –1 Ci yields Ci+1 (following M?s ?) ? Ck is an accepting configuration “uqacceptv” The language that consists of all inputs that are accepted by M is denoted by L(M). 比喻： bool M(w) 最后返回 true Univ. 可計(jì)算理論 2022/8/14 42/88 用格局概念描述 Accepting ep129 ,cp89 A Turing machine M accepts input w??* if and only if there is a finite sequence of configurations C1,C2,…,C k with ? C1 the starting configuration “q0w” ? for all i=1,…,k –1 Ci yields Ci+1 (following M?s ?) ? Ck is an accepting configuration “uqacceptv” The language that consists of all inputs that are accepted by M is denoted by L(M). 比喻： bool M(w) 最后返回 true Univ. 可計(jì)算理論 2022/8/14 43/88 用格局概念描述 Accepting ep129 ,cp89 比喻 錄取 會(huì)議論文 Turing machine M 錄取標(biāo)準(zhǔn)，程序委員會(huì) accepts input w??* 字符串，論文 ， configurations C1,C2,…,C k 評審過程 accepting configuration “uqacceptv” 錄用 uqrejectv” 拒絕 評審無反響 死機(jī) Univ. 可計(jì)算理論 2022/8/14 44/88 Turing Recognizable (Def. ) ep130 cp89 A language L is Turingrecognizable if and only if there is a TM M such that L=L(M). 圖靈可識 : 對 w?L 函數(shù) M(w)返回 true， 對 w?L，無承諾 Note: On an input w?L, the machine M can halt in a rejecting state, or it can ?loop? indefinitely. How do you distinguish between a very long putation and one that will never halt? 問題：如何區(qū)別 長計(jì)算 與 死循環(huán)？ Also called: a recursively enumerable language. L 又稱為 遞歸可枚舉語言 Univ. 可計(jì)算理論 2022/8/14 45/88 Turing Recognizable (Def. ) ep130 cp89 A language L is Turingrecognizable if and only if there is a TM M such that L=L(M). 圖靈可識 : 對 w?L 函數(shù) M(w)返回 true， 對 w?L，無承諾 Note: On an input w?L, the machine M can halt in a rejecting state, or it can ?loop? indefinitely. How do you distinguish between a very long putation and one that will never halt? 問題：如何區(qū)別 長計(jì)算 與 死循環(huán)？ Also called: a recursively enumerable language. L 又稱為 遞歸可枚舉語言 Univ. 可計(jì)算理論 2022/8/14 46/88 Turing Recognizable (Def. ) ep130 cp89 A language L is Turingrecognizable if and only if there is a TM M such that L=L(M). 圖靈可識 : 對 w?L 函數(shù) M(w)返回 true， 對 w?L，無承諾 Note: On an input w?L, the machine M can halt in a rejecting state, or it can ?loop? indefinitely. How do you distinguish between a very long putation and one that will never halt? 問題：如何區(qū)別 長計(jì)算 與 死循環(huán)？ Also called: a recursively enumerable language. L 又稱為 遞歸可枚舉語言 Univ. 可計(jì)算理論 2022/8/14 47/88 Turing Decidable (Def. ) 圖靈可判定 ep130， cp84 Also called: a recursive language. 遞歸語言，比遞歸可枚舉 要求高 A language L=L(M) is decided by the TM M if on every w, the TM finishes in a halting configuration. (That is: qaccept for w?L and qreject for all w?L.) 圖靈可判定 : 對 w?L 函數(shù) M(w) 返回 true， 對 w?L， 返回 false A language L is Turingdecidable if and only if there is a TM M that decides Univ. 可計(jì)算理論 2022/8/14 48/88 Turing Decidable (Def. ) 圖靈可判定 ep130， cp89 Also called: a recursive language. 遞歸語言，比遞歸可枚舉 要求高 A language L=L(M) is decided by the TM M if on every w, the TM finishes in a halting configuration. (That is: qaccept for w?L and qreject for all w?L.) 圖靈可判定 : 對 w?L 函數(shù) M(w) 返回 true， 對 w?L， 返回 false A language L is Turingdecidable if and only if there is a TM M that decides Univ. 可計(jì)算理論 2022/8/14 49/88 Turing Decidable (Def. ) 圖靈可判定 ep130， cp89 Also called: a recursive language. 遞歸語言 ，比遞歸可枚舉 要求高 A language L=L(M) is decided by the TM M if on every w, the TM finishes in a halting configuration. (That is: qaccept for w?L and qreject for all w?L.) 圖靈可判定 : 對 w?L 函數(shù) M(w) 返回 true， 對 w?L， 返回 false A language L i