《唐常杰翻译的计算理论导引-文档资料.ppt》由会员分享，可在线阅读，更多相关《唐常杰翻译的计算理论导引-文档资料.ppt（88页珍藏版）》请在三一文库上搜索。
1、2021/4/5,1,Lecture for Computation Theory,Book :计算理论导引 Introduction to the Theory of Computation Chapter 3 Turing Machine Prof : 唐常杰 TangC Http:/ Students : Phd, MS in CS . 2000- 2006, SCU Style : Lecture / Seminar,2021/4/5,2,Outline for today,Section 3.13.2 : Computability（补充） 3.1 Turing machines T
2、M-computable/recognizable languages 3.2 Variants of TMs （多带机，不确定机）,2021/4/5,3,2021/4/5,4,2021/4/5,5,Intersection a,b,c ; qi,qjQ, and M a TMwith transition function . 格局C1产生格局C2 We say that the configuration “uaqibv” yields the configuration “uacqjb” if and only if: (qi,b) = (qj,c,R). 格局产生 即 格局 按机演化
3、翻译成 格局演进 似更恰当 Similarly, if (qi,b) = (qj,c,L) / 把当前的b改为c 且左移 then “uaqibv” yields “uqjacb” (At the leftmost side of the tape different.),2021/4/5,37,An Elementary TM Step ep129 cp89,Let u,v * ; a,b,c ; qi,qjQ, and M a TMwith transition function . 格局C1产生格局C2 We say that the configuration “uaqibv” yie
4、lds the configuration “uacqjv” if and only if: (qi,b) = (qj,c,R). 格局产生 即 格局 按机演化 翻译成 格局演进 似更恰当 Similarly, if (qi,b) = (qj,c,L) / 把当前的b改为c 且左移 then “uaqibv” yields “uqjacv” (At the leftmost side of the tape different.),2021/4/5,38,Terminology 格局,starting configuration on input w: “q0w” 初始格局 accepting
5、 configuration: “uqacceptv” 接受格局 返回true rejecting configuration: “uqrejectv” 拒绝格局 返回false The accepting and rejecting configurations are the halting configurations.,2021/4/5,39,Terminology 格局,starting configuration on input w: “q0w” 初始格局 accepting configuration: “uqacceptv” 接受格局 返回true rejecting con
6、figuration: “uqrejectv” 拒绝格局 返回false The accepting and rejecting configurations are the halting configurations.,2021/4/5,40,用格局概念描述 Accepting ep129 ,cp89,A Turing machine M accepts input w*if and only if there is a finite sequence of configurations C1,C2,Ck with C1 the starting configuration “q0w” f
7、or all i=1,k1 Ci yields Ci+1 (following Ms ) 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,2021/4/5,41,用格局概念描述 Accepting ep129 ,cp89,A Turing machine M accepts input w*if and only if there is a
8、finite sequence of configurations C1,C2,Ck with C1 the starting configuration “q0w” for all i=1,k1 Ci yields Ci+1 (following Ms ) 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,2021/4/5,42,用格局概念描
9、述 Accepting ep129 ,cp89,A Turing machine M accepts input w*if and only if there is a finite sequence of configurations C1,C2,Ck with C1 the starting configuration “q0w” for all i=1,k1 Ci yields Ci+1 (following Ms ) Ck is an accepting configuration “uqacceptv” The language that consists of all inputs
10、 that are accepted by M is denoted by L(M). 比喻： bool M(w) 最后返回true,2021/4/5,43,用格局概念描述 Accepting ep129 ,cp89,比喻 录取 会议论文 Turing machine M 录取标准，程序委员会 accepts input w* 字符串，论文，configurations C1,C2,Ck 评审过程accepting configuration “uqacceptv” 录用 uqrejectv” 拒绝 评审无反响 - 死机,2021/4/5,44,Turing Recognizable (Def
11、. 3.2) ep130 cp89,A language L is Turing-recognizable if and onlyif there is a TM M such that L=L(M). 图灵可识: 对 wL 函数M(w)返回true， 对wL，无承诺,Note: On an input wL, the machine M canhalt in a rejecting state, or it can loop indefinitely.,How do you distinguish between a very longcomputation and one that wil
12、l never halt? 问题：如何区别 长计算 与 死循环？,Also called: a recursively enumerable language. L 又称为 递归可枚举语言,2021/4/5,45,Turing Recognizable (Def. 3.2) ep130 cp89,A language L is Turing-recognizable if and onlyif there is a TM M such that L=L(M). 图灵可识: 对 wL 函数M(w)返回true， 对wL，无承诺,Note: On an input wL, the machine
13、M canhalt in a rejecting state, or it can loop indefinitely.,How do you distinguish between a very longcomputation and one that will never halt? 问题：如何区别 长计算 与 死循环？,Also called: a recursively enumerable language. L 又称为 递归可枚举语言,2021/4/5,46,Turing Recognizable (Def. 3.2) ep130 cp89,A language L is Turi
14、ng-recognizable if and onlyif there is a TM M such that L=L(M). 图灵可识: 对 wL 函数M(w)返回true， 对wL，无承诺,Note: On an input wL, the machine M canhalt in a rejecting state, or it can loop indefinitely.,How do you distinguish between a very longcomputation and one that will never halt? 问题：如何区别 长计算 与 死循环？,Also
15、called: a recursively enumerable language. L 又称为 递归可枚举语言,2021/4/5,47,Turing Decidable (Def. 3.3)图灵可判定 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 wL and qreject
16、 for all wL.) 图灵可判定: 对 wL 函数M(w) 返回true， 对wL，返回false,A language L is Turing-decidable if and onlyif there is a TM M that decides L.图灵可判定语言,2021/4/5,48,Turing Decidable (Def. 3.3)图灵可判定 ep130， cp89,Also called: a recursive language. 递归语言，比递归可枚举 要求高,A language L=L(M) is decided by the TM M if on every
17、w, the TM finishes in a halting configuration.(That is: qaccept for wL and qreject for all wL.) 图灵可判定: 对 wL 函数M(w) 返回true， 对wL，返回false,A language L is Turing-decidable if and onlyif there is a TM M that decides L.图灵可判定语言,2021/4/5,49,Turing Decidable (Def. 3.3)图灵可判定 ep130， cp89,Also called: a recursi
18、ve 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 wL and qreject for all wL.) 图灵可判定: 对 wL 函数M(w) 返回true， 对wL，返回false,A language L is Turing-decidable if and onlyif there is a TM M that decides L.图灵可判定
19、语言,2021/4/5,50,Exa. 3.4: 判定 A = 0j | j=2n ，n=0 ep131， cp90,Bool M( w) /用C语言模拟TM, 注意不要超标使用资源 if (1 appear in w) return false; j=length(w); loop: If ( j=1) return true; if ( j mod 2=0) i-; goto loop; else return false ; /注意无论 j 为何值，总有结果 ,Check if j=0 or j=1, accept/reject accordingly Check, by going l
20、eft to right if the string haseven or odd number of zeros If odd then “reject” If even then go back left, erasing half the zeros goto 1 算法伪码,2021/4/5,51,Exa. 3.4: 判定 A = 0j | j=2n ep131， cp90,Bool M( j) /用C语言模拟TM, 注意不要超标使用资源 If (j=0) retuen false ; If ( j=1) return true; if ( j mod 2=0) return M(j-1
21、) /这里有点超前，使用了递归 else if (j1) return false ; /注意无论 j 为何值，总有结果 ,Check if j=0 or j=1, accept/reject accordingly Check, by going left to right if the string haseven or odd number of zeros If odd then “reject” If even then go back left, erasing half the zeros goto 1 算法伪码,2021/4/5,52,Exa. 3.4: 判定 A = 0j |
22、 j=2n ep131， cp90,Bool M( j) /用C语言模拟TM, 注意不要超标使用资源 If (j=0) retuen false ; If ( j=1) return true; if ( j mod 2=0) return M(j-1) /这里有点超前，使用了递归 else if (j1) return false ; /注意无论 j 为何值，总有结果 ,Check if j=0 or j=1, accept/reject accordingly Check, by going left to right if the string haseven or odd number
23、 of zeros If odd then “reject” If even then go back left, erasing half the zeros goto 1 算法伪码,2021/4/5,53,State diagrams of TMs,Like with PDA, we can represent Turing machinesby (elaborate) diagrams. See Figures c4.4 and c4.5 for two examples. 见书Ep132, cp85 未画出, 大家一起读书, 建议练习1：把图c4.4 改写成为用goto (而不用递归）
24、的C程序 练习2: 把有递归的程序改为迭代，再转化为图，比较简单，保存中间结果，j-1,以他作输入，重新计算 If transition rule says: qi,b) = (qj,c,R), /读b写c 且右移then:,qi,qj,b c,R,2021/4/5,54,State diagrams of TMs,Like with PDA, we can represent Turing machinesby (elaborate) diagrams. See Figures 3.4 and Fig.3.5 for two examples. 见书Ep132, cp90 未画出, 大家一起
25、读书, 建议练习1：把图3.4 改写成为用goto (而不用递归）的C程序 练习2: 把有递归的程序改为迭代，再转化为图，比较简单，保存中间结果，j-1,以他作输入，重新计算 If transition rule says: (qi,b) = (qj,c,R), /读b写c 且右移then:,qi,qj,b c,R,2021/4/5,55,When Describing TM ep133,书上的例 3.5,3.6, 3.7比较细致，有点繁而不难，学生应仔细读一遍。 课堂上讲较费时，效果不一定好 以后有更高级的方法（例如给出的递归），体会一下低级方法的难处 可 忆苦思甜。,Standard to
26、ols: Expanding the alphabet withseparator “#”, and underlined symbols 0, a, to indicate activity. Typical: = 0,1,#,_,0,1 ,2021/4/5,56,When Describing TM ep133,书上的例 3.5,3.6, 3.7比较细致，有点繁而不难，学生应仔细读一遍。 课堂上讲较费时，效果不一定好 以后有更高级的方法（例如给出的递归），体会一下低级方法的难处 可 忆苦思甜。,Standard tools: Expanding the alphabet withsepar
27、ator “#”, and underlined symbols 0, a, to indicate activity. Typical: = 0,1,#,_,0,1 ,2021/4/5,57,When Describing TM ep133 略,It is assumed that you are familiar with TMs andwith programming computers.,Clarity above all: high level description of TMs is allowed but should not be used as a trick tohide
28、 the important details of the program.,Standard tools: Expanding the alphabet withseparator “#”, and underlined symbols 0, a, to indicate activity. Typical: = 0,1,#,_,0,1 ,2021/4/5,58,3.2 Multitape Turing Machines 多带图灵机 ep136, cp93 增加数组资源，期望编程简单,A k-tape Turing machine M has k differenttapes and rea
29、d/write heads. It is thus defined by the 7-tuple (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 : Qqaccept,qreject k Q k L,Rk 转 写 移,根据K条带上的存储数据现
30、状决定 写，移，转 动作,2021/4/5,59,3.2 Multitape Turing Machines 多带图灵机 ep136, cp93, 增加数组资源，期望编程简单,A k-tape Turing machine M has k differenttapes and read/write heads. It is thus defined by the 7-tuple (Q,q0,qaccept,qreject), with Q finite set of states finite input alphabet (without “_”) finite tape alphabet
31、with _ q0 start state Q qaccept accept state Q qreject reject state Q the transition function : Qqaccept,qreject k Q k L,Rk 转 写 移,根据K条带上的存储数据现状决定 写，移，转 动作,2021/4/5,60,3.2 Multitape Turing Machines 多带图灵机 ep136, cp93, 增加数组资源，期望编程简单,A k-tape Turing machine M has k differenttapes and read/write heads. I
32、t is thus defined by the 7-tuple (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 : Qqaccept,qreject k Q k L,Rk 转 写 移,根据K条带上的存储数据现状决定 写，移，转 动作,202
33、1/4/5,61,k-tape TMs versus 1-tape TMs ep137, cp93,Theorem 3.8: For every multi-tape TM M, thereis a single-tape TM M such that L(M)=L(M). Or, for every multi-tape TM M, there is an equivalent single-tape TM M. 多带机与单带机等价 增加存储和数组(多带)只提速和简化， 无本质改变,Proving and understanding these kinds of robustness res
34、ults, is essential for appreciating the power of the Turing machine model. 称为稳健性,From this theorem Corollary c4.9 follows: A language L is TM-recognizable if and only if some multi-tape TM recognizes L. 以后可用 多带机 作题，简单多了,2021/4/5,62,k-tape TMs versus 1-tape TMs ep137, cp93,Theorem 3.8: For every mult
35、i-tape TM M, thereis a single-tape TM M such that L(M)=L(M). Or, for every multi-tape TM M, there is an equivalent single-tape TM M. 多带机与单带机等价 增加存储和数组(多带)只提速和简化， 无本质改变,Proving and understanding these kinds of robustness results, is essential for appreciating the power of the Turing machine model. 称为
36、稳健性,From this theorem Corollary c4.9 follows: A language L is TM-recognizable if and only if some multi-tape TM recognizes L. 以后可用 多带机 作题，简单多了,2021/4/5,63,k-tape TMs versus 1-tape TMs ep137, cp88,Theorem 3.8: For every multi-tape TM M, thereis a single-tape TM M such that L(M)=L(M). Or, for every mu
37、lti-tape TM M, there is an equivalent single-tape TM M. 多带机与单带机等价 增加存储和数组(多带)只提速和简化， 无本质改变,Proving and understanding these kinds of robustness results, is essential for appreciating the power of the Turing machine model. 称为稳健性,From this theorem Corollary c4.9 follows: A language L is TM-recognizable
38、 if and only if some multi-tape TM recognizes L. 以后可用 多带机 作题，简单多了,2021/4/5,64,Outline Proof Thm. 3.8 ep137, cp95,基本思想：用单磁头 读4声道录音磁带,读出后复制在一条带上，通过mod(4),和数组下标映射，可以标识原产地，但能 算出4带机的任务。内存少一些，程序复杂一点，慢一点。,2021/4/5,65,Outline Proof Thm. 3.8 ep137, cp95,另一种比喻：先写一个有4个数组的C程序,然后写一个只有一个数组的程序去模拟上述程序， 直观上是容易接受的，因为
39、 用下标映射实现模拟的难度不大。 注意，现在下标需要顺序扫描，以后可证明可按下标随机存取图灵机（随机图灵机） 写论文时从来不限制只能用 低级图灵机 证明问题，可以用最先进的工具。 注意力集中在后面将要讨论的 复杂度，P 、 NP问题，不必拘泥与这些技术细节,2021/4/5,66,Outline Proof Thm. 3.8 ep137, cp95,另一种比喻：先写一个有4个数组的C程序,然后写一个只有一个数组的程序区模拟上述程序， 直观上是容易接受的，因为 用下标映射实现模拟的难度不大。 注意，现在下标需要顺序扫描，以后可证明可按下标随机存取图灵机（随机图灵机） 写论文时从来不限制只能用 低
40、级图灵机 证明问题，可以用最先进的工具。 注意力集中在后面将要讨论的 复杂度，P 、 NP问题，不必拘泥与这些技术细节,2021/4/5,67,Outline Proof Thm. 3.8 ep137, cp95模拟结构,造单带机模拟多带机 （多带机模拟单带机不需证明） Let M=(Q,q0,qaccept,qreject) be a k-tape TM. Construct 1-tape M with expanded = # Represent M-configuration u1qja1v1, u2qja2v2, , ukqjakvkby M configuration, qj # u
41、1a1v1 # u2a2v2 # # ukakvk 分带符 #, K道上当前字符,第1道 第k道格局,2021/4/5,68,Outline Proof Thm. 3.8 ep137, cp95模拟结构,造单带机模拟多带机 （多带机模拟单带机不需证明） Let M=(Q,q0,qaccept,qreject) be a k-tape TM. Construct 1-tape M with expanded = # Represent M-configuration u1qja1v1, u2qja2v2, , ukqjakvkby M configuration, qj # u1a1v1 # u
42、2a2v2 # # ukakvk 分带符 #, K道上当前字符,第1道 第k道格局,2021/4/5,69,Proof Thm. 3.8 (cont.) ep137, cp95 模拟动作,On input w=w1wn, the TM M does the following: Prepare initial string: #w1wn#_#_#_ 多带复制到单带 Read the underlined input letters k 各带当前字 Simulate M by updating the input and theunderlining of the head-positions.
43、 通过下标映射模拟动作 Repeat 2-3 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.,2021/4/5,70,Proof Thm. 3.8 (cont.) ep137, cp95 模拟动作,On input w=w1wn, the TM M does the following: Prepare initial string:
44、#w1wn#_#_#_ 多带复制到单带 Read the underlined input letters k 各带当前字 Simulate M by updating the input and theunderlining of the head-positions. 通过下标映射模拟动作 Repeat 2-3 until M has reached a halting state Halt accordingly.,PS: If the update requires overwriting a # symbol,then shift the part # _ one position
45、to the right.,2021/4/5,71,Proof Thm. 3.8 (cont.) ep137, cp95 模拟动作,On input w=w1wn, the TM M does the following: Prepare initial string: #w1wn#_#_#_ 多带复制到单带 Read the underlined input letters k 各带当前字 Simulate M by updating the input and theunderlining of the head-positions. 通过下标映射模拟动作 Repeat 2-3 until
46、 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.,2021/4/5,72,Nondeterministic TMs ep138 cp94 非确定图灵机,A nondeterministic Turing machine M can have several options at every step. It is defined by the 7-
47、tuple (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 : Qqaccept,qreject P (Q L,R),2021/4/5,73,Nondeterministic TMs ep138 cp94 非确定图灵机,A nondeterm
48、inistic Turing machine M can have several options at every step. It is defined by the 7-tuple (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 : Qqaccept,qreject P (Q L,R),2021/4/5,74,Nondeterministic TMs ep138 cp94 非确定图灵机,A nondeterministic Turing machine M can have several options at every step. It is defined by the 7-tuple (Q,q0,qaccept,qreject), with Q finite set of states finite input alphabet (without “_”) finite tape alp