计算理论09_递归哥德尔.ppt

1、1,Part II: Computability Theory,计算理论引论 by Michael Sipser Chapter 7: Recursion Theorem Dr. Weibing Feng ,2,今天课程,Chapter C7: C7.1 Potential Problems with Infinite Recursion Recursion theorem 递归可行性 Undecidability by Self-Reference 自引用 Gdels Incompleteness Theorem 哥德尔不完全定理,3,复习 Undecidability Thus Far c

2、p130,Undecidability thus far used the undecidabilityof the accept problem ATM. 我们已经充分使用了接受问题的不可判定性 We proved the undecidability of ATM by making explicit the self-reference paradox: 采用了自引用集合 S = | TMs M that do not accept 技巧在于（直观解释） 让程序处理自己的源程序： Let P be a TM that recognizes S, then “P on ” leads to

3、 a contradiction. Crucial ingredient: 关键技术 Self-Reference: P accepts .,4,复习 Undecidability Thus Far cp130,Undecidability thus far used the undecidabilityof the accept problem ATM. 我们已经充分使用了接受问题的不可判定性 We proved the undecidability of ATM by making explicit the self-reference paradox: 采用了自引用集合 S = | TM

4、s M that do not accept 技巧在于（直观解释） 让程序分析自己的源程序： Let P be a TM that recognizes S, then “P on ” leads to a contradiction. Crucial ingredient: 关键技术 Self-Reference: P accepts .,5,Self-Reference ep198, cp130,What happens if a computer program M tries toanswer questions about itself ? 程序自己分析自己的源程序会出什么结果？ S

5、ometimes this is perfectly okay:- How big is ?- Is a proper TM? Other questions lead to paradoxes:有时似是而非- Does halt or not?如停机 - Is there a smaller program M that is equivalent?,6,Self-Reference ep198, cp130,What happens if a computer program M tries toanswer questions about itself ? 程序自己分析自己的源程序会出什

6、么结果？ Sometimes this is perfectly okay:- How big is ?- Is a proper TM? Other questions lead to paradoxes:有时似是而非- Does halt or not?如停机 - Is there a smaller program M that is equivalent?,7,Self-Reference ep198, cp130,What happens if a computer program M tries toanswer questions about itself ? 程序自己分析自己的

7、源程序会出什么结果？ Sometimes this is perfectly okay:- How big is ?- Is a proper TM? Other questions lead to paradoxes:有时似是而非- Does halt or not?如停机 - Is there a smaller program M that is equivalent?,8,Avoiding Paradoxes? ep199,paradox 是错误理解的问题。 Maybe自引用的悖论原源自 TM 不能考虑自己 is not able to consider itself? Questio

8、n: How is it possible to have the structure:,How can we havethe completedescription of M inside M itself?,9,Avoiding Paradoxes? Ep199递归,A paradox is a misunderstood problem.Maybe the paradoxes of self-references occurbecause a TM is not able to consider itself? Question: How is it possible to have t

9、he structure:,How can we havethe completedescription of M inside M itself?,在这里调用自己,10,递归,从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事,讲的故事是：”从前有各庙，庙里有个老和尚，老和尚给小和尚将故事,讲的什么故事是” Void story ( ) printf(“从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事,讲的故事是：”)； story( ); 毛病，没有递归深度控制，栈溢出时死机 镜子里面照镜子，电影里面放电影，故事里面讲故事 更新奇的是：,11,递归,从前有个庙，庙里有个老和尚，老和尚给小和尚

10、讲故事,讲的故事是：”从前有各庙，庙里有个老和尚，老和尚给小和尚将故事,讲的什么故事是” Void story ( ) printf(“从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事,讲的故事是：”)； story( ); 毛病，没有递归深度控制，栈溢出时死机 镜子里面照镜子，电影里面放电影，故事里面讲故事 更新奇的是：,12,递归,从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事,讲的故事是：”从前有各庙，庙里有个老和尚，老和尚给小和尚将故事,讲的什么故事是” Void story ( ) printf(“从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事,讲的故事是：”)； story(

11、); 毛病，没有递归深度控制，栈溢出时死机 镜子里面照镜子，电影里面放电影，故事里面讲故事, 庄生梦蝶，更新奇的是：,13,The Droste Effect,It seems impossible tohave a finite object that,as a part, has a complete description of itself. You expect a conflictbetween the finite amountof information-space andthe infinite recursion. 注意这里递归 另例小学一年级语文数封面,14,The Dr

12、oste Effect,It seems impossible tohave a finite object that,as a part, has a complete description of itself. You expect a conflictbetween the finite amountof information-space andthe infinite recursion. 注意这里递归 另例小学一年级语文数封面,15,Infinite Recursion in Math ep200,On the other hand,we know of many (mathem

13、atical)objects that have afinite description, yet appear to be infinitely detailed 分形 数学,16,M Printing M 打印自己源程序 ep200 cp130,问题：自己调用自己的TM是否合法的图灵机 自己调用自己的程序是否合法的程序？ 本节要向证明， 满足一定规范非自己调用是合法的， 从数学本质上看，是正确的， 不是诡辩，不是悖论 而且用途广泛 .,17,M Printing M 打印自己源程序 ep200 cp130,Attempt to describe a program that prints

14、itself: M = print(“print(“print(“print The Droste effect forces M to be infinite.,打印下面语句两个副本，第二次加引号： consider the following high-level program: print_twice_2nd_time_with_(“_“): (“print_twice_2nd_time_with_(“_“):”), So it is possible to have such a TM M.The Recursion Theorem makes this explicit.,18,M

15、 Printing M 打印自己源程序 ep200 cp130,错误方法：Attempt to describe a program that prints itself: M = print(“print(“print(“print The Droste effect forces M to be infinite.,正确方法 打印下面语句两个副本，第二次加引号： consider the following high-level program: print_twice_2nd_time_with_(“_“): (“print_twice_2nd_time_with_(“_“):”), S

16、o it is possible to have such a TM M.The Recursion Theorem makes this explicit.,19,The Recursion Theorem 为定理C7.2（递归的可行性）作准备 ep 200, cp131,The recursion theorem in CS shows how we candeal with the Droste/self-reference effect for TMs. 递归的可行性,The key idea is to split the TM into two parts:1) a string

17、that describes 2nd part of program 获得描述自己的串 （稍难） 2) a program that prints the string smart 打印指定的串 （不难）,How to construct a program that prints itself且看 下面细细道来,20,The Recursion Theorem 为定理C7.2（递归的可行性）作准备 ep 200, cp131,The recursion theorem in CS shows how we candeal with the Droste/self-reference effe

18、ct for TMs. 递归的可行性,The key idea is to split the TM into two parts:1) a string that describes 2nd part of program 获得描述第二部分串 （稍难） 2) a program that prints the string smart 打印指定的串 （不难）,How to construct a program that prints itself且看 下面细细道来,21,A Simple Lemma cp130,Lemma C7.1 : Let w be an input string,

19、and let Pw be a TM that prints w. The function q(w) = is TM computable. 打印指定串的程序的源程序是 可以用程序产生的,证明 程序 Pw(x) x0=0; printf(w); /总是打印外部串W q:* *, 使得 q(w)=“ Pw(x) x0=0; printf(w);” 造计算q的TM Q (C程序)如下： Q(w ) char *p=q(w);/函数值是一个源程序串的指针 printf(p); 下页是书上的证明,22,A Simple Lemma cp130,Lemma C7.1 : Let w be an inp

20、ut string, and let Pw be a TM that prints w. The function q(w) = is TM computable. 打印指定串的程序的源程序是 可以用程序产生的,证明 程序 Pw(x) x0=0; printf(w); /总是打印外部串W q:* *, 使得 q(w)=“ Pw(x) x0=0; printf(w);” 造计算q的TM Q (C程序)如下： Q(w ) char *p=q(w);/函数值是一个源程序串的指针 printf(p); 下页是书上的证明,23,A Simple Lemma ， cp130 书上的证明,Lemma C7.

21、1 : Let w be an input string, and let Pw be a TM that prints w. The function q(w) = is TM computable. 打印指定串的程序的源程序是 可以用程序产生的,Proof: Consider the TM (on input w):1) Construct TM Pw: 1) erase input 2) write w and halt 2) Output ,24,利用引理，造一个能打印自己源程序的程序The Program = ep201 cp130,用C语言描述 库函数 B() Get_source

22、_as( ,P)；/反编译 printf(“%s%s”,P,); main(char argv , int argc ) / 输入w 为 argv1=w char *A=;/B的源程序,如用argv0即EXE名,复制串 B(); 下页是书上的证明,输入TM , 输出：源程序串,25,利用引理，造打印自己源程序的程序The Program = ep201 cp130,The SELF-program consists of two parts A and B: First part: A = P, so we will wait with this one B part (on input wi

23、th M a TM subroutine):1) Read , compute % see Lemma 6.12) Use and to print M Now we know what P looks like.,26,Working of SELF: ep201,P 1) Given , compute /反编译 2) Use and to print M,After A-part on the tape: 1) Given . . . M,B1 reads input on tape, computes ,B2 prints:P 1) Given . . . M,A =B1 =B2 =,

24、B1,B2的串,27,Recursion Theorem ep200,Instead of printing, a TM can do anything elsewith its own description. 可以把打印 ( printf ) 改成其他任何处理，如加密，例如下面的 t 可以是个串加密函数,Recursion Theorem (6.2): Let t: * be a TM-computable function. There is a Turing machine R that computes the function r: *with r(w) = t(,w) for e

25、very w*.,(In the case of SELF, we had t(x,y) = x.),28,Recursion Theorem ep200,Instead of printing, a TM can do anything elsewith its own description. 可以把打印 ( printf ) 改成其他任何处理，如加密，例如下面的 t 可以是个串加密函数,Recursion Theorem (6.2): Let t: * be a TM-computable function. There is a Turing machine R that comput

26、es the function r: *with r(w) = t(,w) for every w*.,(In the case of SELF, we had t(x,y) = x.),29,Recursion Theorem ep200, cp131,Recursion Theorem (C7.2): Let t: * be a TM-computable function. There is a Turing machine R that computes the function r: * with r(w) = t(,w) for every w*. C描述的证明: 已经有了程序 T

27、(w) 加密 .，现在如下造程序R: R(w) char *s=; /R自己的 源程序或代码，前面已经证明可得 s=s+w; /或用strcat T(S); 意义：R把自己的源程序作为处理的首部，当w=NULL时，R自己处理自己（注意由于T是任何程序，例如是加密程序，则R把自己加密） 下页是书上的证明,30,Recursion Theorem ep200, cp131,Recursion Theorem (C7.2): Let t: * be a TM-computable function. There is a Turing machine R that computes the func

28、tion r: * with r(w) = t(,w) for every w*. C描述的证明: 已经有了程序 T(w) 加密 .，现在如下造程序R: R(w) char *s=; /R自己的 源程序或代码，前面已经证明可得 s=s+w; /或用strcat T(S); 意义：R把自己的源程序作为处理的首部，当w=NULL时，R自己处理自己（注意由于T是任何程序，例如是加密程序，则R把自己加密） 下页是书上的证明,31,Recursion Theorem ep200, cp131,Recursion Theorem (C7.2): Let t: * be a TM-computable fu

29、nction. There is a Turing machine R that computes the function r: * with r(w) = t(,w) for every w*. C描述的证明: 已经有了程序 T(w) 加密 .，现在如下造程序R: R(w) char *s=; /R自己的 源程序或代码，前面已经证明可得 s=s+w; /或用strcat T(S); 意义：R把自己的源程序作为处理的首部，当w=NULL时，R自己处理自己（注意由于T是任何程序，例如是加密程序，则R把自己加密） 下页是书上的证明,32,Proof Recursion Theorem6.2 ep

30、200 cp131 书上的证明，稍难理解,Let t: * be a TM-computable function. There is a TM R that computes the function r(w) = t(,w) for every w*.,Proof: Let T be the TM that computes t.The TM R consists of 3 parts: A,B,T (input w):A = P B = Read input , print M T = Calculate t on (tape content,w).,33,Application Rec

31、ursion Thm cp131-132,The recursion theorem makes it clear that self-reference is possible for TMs: TM可自己调自己 is possible. It shows that programs like SELF are possible. Makes undecidability proofs more transparentas they can now be phrased for a single TM.,1) Bla-bla-bla;平凡简单 2) Look at ; 3) More Bla

32、-bla-bla;,M =,34,ATM is Undecidable 用新式武器来证明旧问题 定理6.3 ep202,Proof by contradiction: 用C语言描述设bool Deter_Accept(M ,w)是接受判定程序，造 TM B ( w)如下： bool B ( w) printf (); /打印自己的源程序 OK = ! Deter_Accept(B,W); /递归 return OK /如果B接受w, OK=false, 则B不接受w, 下页是书上的证明,Theorem C7.3: The acceptance language ATM = | TM M acc

33、epts input w is undecidable. 接受问题是不可判定的,35,ATM is Undecidable 用新式武器来证明旧问题 定理6.3 ep202,Proof by contradiction: 用C语言描述设bool Deter_Accept(M ,w)是接受判定程序，造 TM B ( w)如下： bool B ( w) / Deter_Accept(B,W） printf (); /打印自己的源程序 OK = ! Deter_Accept(B,W); /递归 return OK /如果B接受w, OK=false, 则B不接受w,矛盾 下页是书上的证明,Theore

34、m C7.3: The acceptance language ATM = | TM M accepts input w is undecidable. 接受问题是不可判定的,Deter_Accept(M,x)对任何M,x都能判定，对特殊的M=B,x=w当然也能,36,ATM is Undecidable 用新式武器来证明旧问题 定理6.3 ep202,Proof by contradiction:书上的证明 Assume that H decides ATM. Construct the following TM B (input w):1) Print own description 2)

35、 Run H on input 3) Negate answer of H,Theorem C7.3: The acceptance language ATM = | TM M accepts input w is undecidable. 接受问题是不可判定的,The answer of H on and the replyof B on will disagree. Contradiction.,37,上述方法的窍门,The previous proof gives a TM-computable counterexample for every H attempt. 用 自调用否定 导出

36、矛盾,For every TM H that claims to decide ATM,construct the following TM B (input w):1) Print own description 2) Run H on input 3) Negate answer of H,It doesnt require a human to come up witha counterexample for H,38,定理C7.5 cp132,MINTM=|M是极小TM,等价TM中最短 定理C7.5 MINTM不可判定 自学。,39,C7.2 Mathematical Theories

37、 ep204， cp133 计划自学内容，略讲,The theory of (un)decidability helps us to understand the limitations of logical theories. 不可判定问题表明逻辑的局限性,Consider some statements about the natural numbers N=0,1,2,: q p x,y pq 如果 MTh(N,+,), 则 M is true ，and M doesnot reject M. 与M的构造定义矛盾 与前几周证明的类似，这次更细致一些，,59,Proof Incomplet

38、eness Thm (2),把 M = (rejecting computing history of M on M) 形式化表达为 M = C REJECT(M,M)(C) 利用递归定理和一些技巧 （some smart tricks）用Th(N,+,)的术语表达函数 REJECT(M,M)，则 M=C REJECT(M,M)(C) 也是系统 Th(N,+,)中的一个语句. 如果 MTh(N,+,) (“is true”) 则 M 拒绝 M; 如果 MTh(N,+,), 则 M is true ，and M doesnot reject M. 与M的构造定义矛盾 与前几周证明的类似，这次更细

39、致一些，,60,The Consequences? cp137,For any axiomatic description D of Th(N,+,),we can make a statement D that we cannot prove with D. We can expand the D with D or with D. Cf. Euclidean and non-Euclidean geometry:欧氏集合与非欧几何 “The sum of the angles of a triangle is equal to two right angles.”,61,The Conse

40、quences? cp137,62,Expanding the TM Model oracle 喻示,请圣贤帮忙，请专家顾问帮忙,Just as any mathematical theory, we can expandour Turing machine model for computation. We can ask the question:What can we compute with a Turing machineif (for some reason) we know the set ATM? Usually this is phrased in terms of an e

41、xternaloracle 喻示，圣贤 直观解释：有无穷个CPU的并行机 cp139 OS that answers questions “xS?”,63,Expanding the TM Model oracle 喻示,请圣贤帮忙，请专家顾问帮忙,Just as any mathematical theory, we can expandour Turing machine model for computation. We can ask the question:What can we compute with a Turing machineif (for some reason) we know the set ATM? Usually this is phrased in terms of an externaloracle 喻示，圣贤 直观解释：有无穷个CPU的并行机 cp139 OS that answers quest