06B_05d1_reduction-100114.ppt

《06B_05d1_reduction-100114.ppt》由会员分享，可在线阅读，更多相关《06B_05d1_reduction-100114.ppt（76页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、CS_Dept.Sichuan Univ.可计算理论Lecture Notes for ComputationBook:计算理论导引 Introduction to the Theory of Computation Chap5 Reductions(可归约性）可归约性）Professor:唐常杰TangC Http:/ Students :Ph.D.2000-2009,SCUStyle :Lecture/Seminar 2023/1/221CS_Dept.Sichuan Univ.可计算理论 2023/1/222CS_Dept.Sichuan Univ.可计算理论 2023/1/223CS_

2、Dept.Sichuan Univ.可计算理论Outline for todaySection 5.1:5.1 Reductions Examples of undecidable languages Computation histories More complex reductions2023/1/224CS_Dept.Sichuan Univ.可计算理论复习复习 Last lesson co-TM recognizable 语言族TM-recognizable 语言族 TM decidableETM=M|M is a TM with L(M)=EQTM=G,H|G,H TMs with

3、 L(G)=L(H)ATM=M,w|M is a TM that accepts w 2023/1/225CS_Dept.Sichuan Univ.可计算理论关于规约的故事关于规约的故事(1/3)1/3)改写改写路沙路沙.彼得彼得(RozesRozes Peter)Peter)的的 故事故事nTask 1(煤气灶,水龙头，空水壶 火柴)n输入：煤气灶 水龙头，火柴,空水壶n输出：开水nStep:n1 空水壶 加水n2 火柴 对煤气灶 点火 n3 水壶 Over 煤气灶 OK可以让机器人执行2023/1/226CS_Dept.Sichuan Univ.可计算理论关于规约的故事(2/3)nTask

4、 2(煤气灶 水龙头，已经有水的水壶,火柴)n输入：煤气灶，水龙头，火柴 已经有水的水壶n输出：开水nStep:n2火柴 对煤气灶 点火 n3水壶 Over 煤气灶 错！让机器人执行较困难，需要较高智能去判断2023/1/227CS_Dept.Sichuan Univ.可计算理论关于规约的故事(2/3)nTask 2(煤气灶 水龙头，已经有水的水壶,火柴)n输入：煤气灶，水龙头，火柴 已经有水的水壶n输出：开水nStep:n2火柴 对煤气灶 点火 n3水壶 Over 煤气灶 错！让机器人执行较困难，需要较高智能去判断2023/1/228CS_Dept.Sichuan Univ.可计算理论关于规

5、约的故事(3/3)nTask3(煤气灶，水龙头，已经有水的水壶,火柴)n输入：煤气灶，水龙头，火柴,已经有水的水壶n输出：开水nStep:n 1 把水壶中的水到掉 ;把问题规约为空水壶问题n 2 call Task1(煤气灶,水龙头，空水壶 火柴)n这才是 问题的 规约 方案！OK机器人执行较容易，按预案办2023/1/229CS_Dept.Sichuan Univ.可计算理论Standard Reflex 标准反射When thinking about a language L:成员藉 For every wL,will there be a proof of this?For every

6、wL,will there be a proof of this?It is usually not hard to prove that L is TM or co-TM recognizable.证明可识别或可协同识别较易（原因，可数集，容易一个个分析）The second part that says“L is not decidable”,or“L is not TM or co-TM recognizable”is harder.证明不可判定较难，原因，不可数个，集合太大需要引入新的方法2023/1/2210CS_Dept.Sichuan Univ.可计算理论Standard Ref

7、lex 标准反射When thinking about a language L:成员藉 For every wL,will there be a proof of this?For every wL,will there be a proof of this?It is usually not hard to prove that L is TM or co-TM recognizable.证明可识别或可协同识别较易（原因，可数集，容易一个个分析）The second part that says“L is not decidable”,or“L is not TM or co-TM rec

8、ognizable”is harder.证明不可判定较难，原因，不可数个，比较复杂需要引入新的方法2023/1/2211CS_Dept.Sichuan Univ.可计算理论Chapter 5:Reducibility Chapter 5:Reducibility 可归约性可归约性一种一种 化难为易化难为易 化繁为简化繁为简 的方法的方法 ,ep173ep173，cp118 cp118 补充补充归约的直观解释：调用问题 A官,B兵,对应C程序(TM)：Prog_官(w),Prog_兵(w)如果 官调 兵 如下：Prog_官(w)./简单计算 Prog_兵(w)/简单计算 则称官 规约为 兵,从计

9、算能力比较有 官=兵 主调 被调 如果 B兵 能识别语言 L，则A官 也能逆否定理 如果A官不能识别L,则B兵 也不能 我们用这一条被调用者为核心技术2023/1/2212CS_Dept.Sichuan Univ.可计算理论Chapter 5:Reducibility Chapter 5:Reducibility 可归约性可归约性一种一种 化难为易化难为易 化繁为简化繁为简 的方法的方法 ,ep173ep173，cp118cp118归约的直观解释：调用，问题 A官,B兵,对应C程序(TM)：Prog_官(w),Prog_兵(w)如果 官调 兵 如下：Prog_官(w)./简单计算 Prog_兵

10、(w)/简单计算 则称官 规约为 兵,从计算能力比较有 官=兵 主调 被调 如果 B兵 能识别语言 L，则A官 也能逆否定理 如果A官不能识别L,则B兵 也不能，我们用这一条被调用者为核心技术2023/1/2213CS_Dept.Sichuan Univ.可计算理论Halting Problem Revisited ep.172 原来把 ATM=M,w|the TM M 识别 w 称为 停机问题 是因为它与下列 名副其实的停机问题 很近 ATM 应该称为 接受问题,A-Accept（见c112脚注）名副其实的停机问题:Theorem C6.1:The halting problem langu

11、age HALTTM=M,w|the TM M halts on input w is undecidable(but of course recognizable).M 接受w M拒绝w M在w死循环接受问题分界线 停机问题 分界线 2023/1/2214CS_Dept.Sichuan Univ.可计算理论Halting Problem Revisited ep.172 原来把 ATM=M,w|the TM M 识别 w 称为 停机问题 是因为它与下列 名副其实的停机问题 很近 ATM 应该称为 接受问题,A-Accept（见c112脚注）名副其实的停机问题:Theorem C6.1:The

12、 halting problem language HALTTM=M,w|the TM M halts on input w is undecidable(but of course recognizable).M 接受w M拒绝w M在w死循环接受问题分界线 停机问题 分界线 2023/1/2215CS_Dept.Sichuan Univ.可计算理论Halting Problem Revisited ep.172理论的意义：知道是不可判定问题，就不要浪费力量去编程序，可把问题特化，解决小一点的 子问题用C语言表示的函数原型：bool Deter_Accept()/接受问题True 表示M接受

13、w，false 不接受，可能 死循环Bool Deter_Halt()/停机问题false 表示M在W 死循环，true:接受或拒绝2023/1/2216CS_Dept.Sichuan Univ.可计算理论Halting Problem Revisited ep.172理论的意义：知道是不可判定问题，就不要浪费力量去编程序，可把问题特化，解决小一点的 子问题用C语言表示的函数原型(SCU CS的约定方法符号）引入下列符号：bool Deter_Accept()/接受问题 判定器True 表示M接受w，false 不接受，可能 死循环Bool Deter_Halt()/停机问题 判定器false

14、 表示M在W 死循环，true:接受或拒绝2023/1/2217CS_Dept.Sichuan Univ.可计算理论Halting Problem Revisited Halting Problem Revisited ep.172 cp118ep.172 cp118停机问题不可判定停机问题不可判定 ，我们的证明，比书上直观一些我们的证明，比书上直观一些Theorem C6.1:The halting problem language HALTTM=M,w|the TM M halts on input w is undecidable(but of course recognizable).

15、Proof:反证法 下页2023/1/2218CS_Dept.Sichuan Univ.可计算理论Halting Problem Revisited Halting Problem Revisited ep.172 cp118ep.172 cp118停机问题不可判定停机问题不可判定 ，我们的证明，比书上直观一些我们的证明，比书上直观一些Proof:反证法 反设存在判定器 Deter_Halt 判定 HALTTM./书上的G The following TM Deter_Accept decides ATM:bool Deter_Accept()/判定接受问题 if(Deter_Halt()/停

16、机问题 return(M(w)/M接受,返回true,否则 false 如停机问题能判定，则与以前结论 接受问题不可判定（对某些w,会死循环)，矛盾。证毕。当官当兵2023/1/2219CS_Dept.Sichuan Univ.可计算理论Halting Problem Revisited Halting Problem Revisited ep.172 cp118ep.172 cp118停机问题不可判定停机问题不可判定 ，我们的证明，比书上直观一些我们的证明，比书上直观一些Proof:反证法 反设存在判定器 Deter_Halt 判定 HALTTM./书上的G The following TM

17、 Deter_Accept decides ATM:bool Deter_Accept()/判定接受问题 if(Deter_Halt()/停机问题 return(M(w)/M接受,返回true,否则 false 如停机问题能判定，则与以前结论 接受问题不可判定（对某些w,会死循环)，矛盾。证毕。当官当兵2023/1/2220CS_Dept.Sichuan Univ.可计算理论Halting Problem Revisited Halting Problem Revisited ep.172 cp118ep.172 cp118书上的证明，严格一些书上的证明，严格一些 略，自学略，自学Theore

18、m 5.1:The halting problem language HALTTM=M,w|the TM M halts on input w is undecidable(but of course recognizable).Proof:Let G be a TM that decides HALTTM.The following TM decides ATM:1.On input M,w run G to decide halting2.If G rejected M,w then“reject”3.If G accepted M,w then copy(reject/accept)ou

19、tput of M on w.(Note that this TM always produces an output.)ATM is undecidable,hence such a G cannot exist.2023/1/2221CS_Dept.Sichuan Univ.可计算理论Halting Problem Revisited Halting Problem Revisited ep.172 cp118ep.172 cp118书上的证明，严格一些书上的证明，严格一些 略，自学略，自学Theorem 5.1:The halting problem language HALTTM=M,

20、w|the TM M halts on input w is undecidable(but of course recognizable).Proof:Let G be a TM that decides HALTTM.The following TM decides ATM:1.On input M,w run G to decide halting2.If G rejected M,w then“reject”3.If G accepted M,w then copy(reject/accept)output of M on w.(Note that this TM always pro

21、duces an output.)ATM is undecidable,hence such a G cannot exist.2023/1/2222CS_Dept.Sichuan Univ.可计算理论Emptiness Testing(1)ep173 CP 119ep173 CP 119Theorem 5.2:The language of non-accepting TMs ETM=M|M is a TM with L(M)=is not decidable(but co-TM recognizable).空接受 问题 不可判定Reduction proof:反证法，设ETM 可判定 AT

22、M可判定矛盾。设ETM可判定，且 G be a TM that decides ETMC语言表达法最易理解（然后看书上的）预备：给定M,w,容易造TM M1 对应于下列函数 bool M1(x)if(x=w)return M(x);/如果用C表达，已完工了，即书上cp113,倒数1行的M1尖括号表示编码或源程序2023/1/2223CS_Dept.Sichuan Univ.可计算理论Emptiness Testing(1)ep173 CP 119ep173 CP 119Theorem 5.2:The language of non-accepting TMs ETM=M|M is a TM w

23、ith L(M)=is not decidable(but co-TM recognizable).空接受 问题不可判定Reduction proof:反证法大致思路，设ETM 可判定 ATM可判定矛盾。2023/1/2224CS_Dept.Sichuan Univ.可计算理论Emptiness Testing(1)ep173 CP 119ep173 CP 119预备工作的比喻 造一个函数 Sin(X)if x=1 (X)=0,if X 1 只在一处模仿Sin 其余均 0 2023/1/2225CS_Dept.Sichuan Univ.可计算理论Emptiness Testing(1)ep17

24、3 CP 119ep173 CP 119设ETM可判定，且 G be a TM that decides ETMC语言表达法最易理解（然后看书上的）给定M,w,容易造TM M1 对应于下列函数 bool M1(x)if(x=w)return M(x);else return false;，/false=reject 类似数学中的函数在M1输入且接受w为ture,其余 拒绝即书上cp119,倒数1行的M1 源程序=“if(x=w)return M(x);else return false;”预备工作：M1只在一处模仿M,其余均拒绝 2023/1/2226CS_Dept.Sichuan Univ.

25、可计算理论Emptiness Testing(1)ep173 CP 119ep173 CP 119判定ATM的TM 记为 boot Deter_Accept()判定 空问题ETM 的TM 记为 boor Deter_Emptyt()构造调用(归约)：bool Deter_Accept()=“if(x=w)return M(x);else return false;”/false=reject return(Deter_Emptyt()如果 被调者 判定，则主调者 也 判定，与接受问题不可判定 矛盾 被调者的输入 是源程序，它只在x=w时才有返回值。如果主调程序返回了值，一定是M1识别不空，由M

26、1的构造，M接受X2023/1/2227CS_Dept.Sichuan Univ.可计算理论Emptiness Testing(1)ep173 CP 119 ep173 CP 119，比书上易理解，比书上易理解判定接受的TM 记录为 boot Deter_Accept()判定接受的空问题ETM的TM 记为 boor Deter_Emptyt()构造调用(归约)：Boo l Deter_Accept()=“if(x=w)return M(x);else return false;”/false=reject return(Deter_Empty()被调者的输入 是源程序，它只在x=w时才有返回值

27、。语言不空主调程序返回了ture，是M1识别不空由M1的构造，M接受X 接受问题可判定如果 被调者 判定，则主调者 也 判定，与接受问题不可判定 矛盾2023/1/2228CS_Dept.Sichuan Univ.可计算理论Emptiness Testing(1)ep173 CP 119 ep173 CP 119，比书上易理解，比书上易理解判定接受的TM 记录为 boot Deter_Accept()判定接受的空问题ETM的TM 记为 boor Deter_Emptyt()构造调用(归约)：Boo l Deter_Accept()=“if(x=w)return M(x);else return

28、 false;”/false=reject return(Deter_Empty()如果 被调者 判定，则主调者 也 判定，与接受问题不可判定 矛盾 被调者的输入 是源程序，它只在x=w时才有返回值。语言不空主调程序返回了ture，是M1识别不空由M1的构造，M接受X 接受问题可判定2023/1/2229CS_Dept.Sichuan Univ.可计算理论Emptiness Testing(2)Emptiness Testing(2)Proof:Given M,w,define the TM PMw by:上页中=“if(x=w)return M(x)”书上的叙述为PMw=“On input

29、x:1.If xw then“reject”2.If x=w then run M on w 相当于M13.If M accepts w then“accept”By construction:Either L(PMw)=w if and only if M accepts w,or L(PMw)=if and only if M does not accept w.Deciding“PMwETM?”decides“M,wATM?”尖括号表示编码或源程序2023/1/2230CS_Dept.Sichuan Univ.可计算理论Emptiness Testing(2)Emptiness Test

30、ing(2)Proof:Given M,w,define the TM PMw by:上页中=“if(x=w)return M(x)”书上的叙述为PMw=“On input x:1.If xw then“reject”2.If x=w then run M on w 相当于M13.If M accepts w then“accept”By construction:Either L(PMw)=w if and only if M accepts w,or L(PMw)=if and only if M does not accept w.Deciding“PMwETM?”decides“M,w

31、ATM?”2023/1/2231CS_Dept.Sichuan Univ.可计算理论Emptiness Testing(3)Emptiness Testing(3)完整的证明，不如完整的证明，不如C C写的简洁写的简洁Final proof:Let G be a TM that decides ETM.Consider the following TM on input M,w1)Construct TM PMw/即“if(x=w)return M(x)”2)Run G on PMw3)If G accepts PMw then“reject”M,w4)If G rejects PMw the

32、n“accept”M,wBecause:PMw ETM M accepts w M,wATMthe above TM decides ATM,this TM cannot exist.Conclusion:ETM is not TM-decidable.2023/1/2232CS_Dept.Sichuan Univ.可计算理论Emptiness Testing(3)Emptiness Testing(3)完整的证明，不如完整的证明，不如C C写的简洁写的简洁Final proof:Let G be a TM that decides ETM.Consider the following TM

33、on input M,w1)Construct TM PMw/即“if(x=w)return M(x)”2)Run G on PMw3)If G accepts PMw then“reject”M,w4)If G rejects PMw then“accept”M,wBecause:PMw ETM M accepts w M,wATMthe above TM decides ATM,this TM cannot exist.Conclusion:ETM is not TM-decidable.2023/1/2233CS_Dept.Sichuan Univ.可计算理论Rices Theorem

34、(习题习题 5.28 5.28，第二版新增第二版新增 答案答案 稍有不同稍有不同)准备讨论 定理.3 ,cp114RegularTM=M|L(M)is a regular language 直观解释：一切能识别正则语言的图灵机的源程序的集合。(毛病在于“一切”)以及类似的 FiniteTM=M|L(M)is a finite language CFGTM=M|L(M)is a CFG language 要证明它们都是不可判定语言。一个个证明太麻烦，它们有共同规律：SOMETM=M|L(M)with Some property 先补充一个Rices定理，把他们统一解决2023/1/2234CS_

35、Dept.Sichuan Univ.可计算理论Rices Theorem(习题习题 .2.2)准备讨论 定理.3 ,cp114RegularTM=M|L(M)is a regular language 直观解释：能识别一切正则语言的图灵机的的源程序的集合。(毛病在于“一切”)以及类似的 FiniteTM=M|L(M)is a finite language CFGTM=M|L(M)is a CFG language 要证明它们都是不可判定语言。一个个证明太麻烦，它们有共同规律：SOMETM=M|L(M)with Some property 先补充一个Rices定理，把他们统一解决2023/1/

36、2235CS_Dept.Sichuan Univ.可计算理论Rices Theorem(习题习题 5.2 5.2)准备讨论 定理.3 ,cp120RegularTM=M|L(M)is a regular language 直观解释：一切能识别正则语言的图灵机的集合。(毛病在于“一切”)以及类似的 FiniteTM=M|L(M)is a finite language CFGTM=M|L(M)is a CFG language 要证明它们都是不可判定语言。一个个证明太麻烦，它们有共同规律：SOMETM=M|L(M)with Some property 先补充一个Rices定理，把它们统一解决20

37、23/1/2236CS_Dept.Sichuan Univ.可计算理论Rices Theorem (习题习题5.28,5.28,第二版书有解答第二版书有解答)Consider the generic TM-related languageL=M|M is a TM for which something holds 直观:L是一切有某性质的图灵机编码（如源程序）的集合Rices Theorm:If this something is such that1)Langu(M1)=Langu(M2)implies“M1L M2L”语言中串（TM源程序）的 等效程序也是成员2)There are tw

38、o TMs M1 and M2 with M1L and M2L (The language L is non-trivial.)该语言L 非空 非全Then the language L is undecidable.则L不可判定 z2023/1/2237CS_Dept.Sichuan Univ.可计算理论Rices Theorem(Problem 5.28)Consider the generic TM-related languageL=M|M is a TM for which something holds 直观:L是有某性质的一切图灵机编码（如源程序）的集合Rices Theorm

39、:If this something is such that1)Langu(M1)=Langu(M2)implies“M1L M2L”2)2)There are two TMs M1 and M2 with M1L and M2L (The language L is non-trivial.)Then the language L is undecidable.图灵机编码性质1 等价机器的 编码串 的 成员籍 相同性质2 该语言L 非空,非全结论：L 不可判定2023/1/2238CS_Dept.Sichuan Univ.可计算理论Rices Theorem(Problem 5.28)Co

40、nsider the generic TM-related languageL=M|M is a TM for which something holds 直观:L是有某性质的一切图灵机编码（如源程序）的集合Rices Theorm:If this something is such that1)Langu(M1)=Langu(M2)implies“M1L M2L”2)2)There are two TMs M1 and M2 with M1L and M2L (The language L is non-trivial.)Then the language L is undecidable.

41、图灵机编码性质1 等价机器的 编码串 的 成员籍 相同性质2 该语言L 非空,非全结论：L 不可判定2023/1/2239CS_Dept.Sichuan Univ.可计算理论Rices Theorem(Problem 5.28)Consider the generic TM-related languageL=M|M is a TM for which something holds 直观:L是有某性质的一切图灵机编码（如源程序）的集合Rices Theorm:If this something is such that1)Langu(M1)=Langu(M2)implies“M1L M2L”

42、2)2)There are two TMs M1 and M2 with M1L and M2L (The language L is non-trivial.)Then the language L is undecidable.图灵机编码性质1 等价机器的 编码串 的 成员籍 相同性质2 该语言L 非空,非全结论：L 不可判定2023/1/2240CS_Dept.Sichuan Univ.可计算理论Rices Theorem(Problem 5.28)用SCU表达方式：用C语言来 表达证明,因为已知L非空非全，所以存在TM Q 使得!=L(Q)L反设 L是可判定的，则对具体的Q,L(Q)L

43、是可判定的接受问题可实现如下：Bool Deter_Accept()/造TM PMW,其源程序如下：=“if(M(x)return(Q(x)else reject x”return(PMW(W);/完成了该问题向接受问题的规约 分析，如果 M 拒绝 w 或在w死循环,则 L(PMw)=，如果M 接受 W,L(PMw)=L(Q),所以 判定“PMwL?”判定“M,wATM?”矛盾。下页是传统的证明方法：在程序中动态写一个程序，然后运行，类似 JSP,ASP2023/1/2241CS_Dept.Sichuan Univ.可计算理论Rices Theorem(Problem 5.28)用SCU表达方

44、式：用C语言来 表达证明,因为已知L非空非全，所以存在TM Q 使得!=L(Q)L反设L是可判定的，则对具体的Q,L(Q)L是可判定的接受问题可实现如下：Bool Deter_Accept()/造TM PMW,其源程序如下：=“if(M(x)return(Q(x)else reject x”return(PMW(W);/完成了该问题向接受问题的归约 分析，如果 M 拒绝 w 或在w死循环,则 L(PMw)=，从而 PMw L，如果M 接受 W,L(PMw)=L(Q)，所以PMwL,于是 判定“PMwL?”判定“M,wATM?”，与接受问题不可判定矛盾。下页 传统证法表达在程序中动态写一个程序，

45、然后运行，类似 JSP,ASP2023/1/2242CS_Dept.Sichuan Univ.可计算理论Proof Idea Rices Theorem Proof Idea Rices Theorem 证明的思路证明的思路 ep175,ep175,cp114 cp114 可可自学自学下面是取自参考资料上的证明 的表达方法 自学反证法 Assume that there is a TM G that decides L如以前证明 空问题 时，已知接受问题 ATM对输入 M,w是不可判定的，让ATM调用一个 TM Pw，使得 判定“PMwL?”判定“M,wATM?”，从而矛盾PMw:M acce

46、pts w?act like Lact like L2023/1/2243CS_Dept.Sichuan Univ.可计算理论Proving Rice cont.可自学可自学Proof:Given M,w,define the TM PMw by:PMw=“On input x:1.Run M on w2.If M rejected then“reject”x3.If M accepted then run Q on xBy construction:If M on w rejects or never stops:L(PMw)=If M accepts w:L(PMw)=L(Q)Decidi

47、ng“PMwL?”decides“M,wATM?”TMs with empty language are either in L or not.Let Q be a TM such that Q is in opposite set.2023/1/2244CS_Dept.Sichuan Univ.可计算理论Final Proof Rices Theorem 自学自学(Take TMs with language L,and QL.)Let G be a TM that decides L.The following TM would decide ATM(input M,w):1)Given

48、M and w,make PMw as described before2)Give same answer as G on PMwCorrectness proof:-If M accepts w:L(PMw)=L(Q),hence PMwL-If M does not accept w,then L(PMw)=:PMwLContradiction if G indeed decides“PMwL?”(If QL,then negate answer of G,et cetera.)2023/1/2245CS_Dept.Sichuan Univ.可计算理论Consequences of Ri

49、ces Consequences of Rices ThmThm.一系列重要推论一系列重要推论Almost any language property of Turing machinesis undecidable:定理5.3 cp120RegularTM=M|L(M)is a regular language 一切识别正则语言的图灵机集合FiniteTM=M|L(M)is a finite language 一切识别有限语言的图灵机集合 CFGTM=M|L(M)is a CFG language 一切识别CFG语言的图灵机集合2023/1/2246CS_Dept.Sichuan Univ.

50、可计算理论Consequences of Rices Consequences of Rices ThmThm.一系列重要推论一系列重要推论Almost any language property of Turing machinesis undecidable:定理5.3 cp120RegularTM=M|L(M)is a regular language 一切识别正则语言的图灵机集合FiniteTM=M|L(M)is a finite language 一切识别有限语言的图灵机集合 CFGTM=M|L(M)is a CFG language 一切识别CFG语言的图灵机集合2023/1/22