计算理论09_递归哥德尔

1、可计算理论1 计算理论引论计算理论引论 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 us

2、ed the undecidability of 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 a contradiction. Crucial ingr

3、edient: 关键技术 Self-Reference: P accepts . 可计算理论4 Undecidability thus far used the undecidability of 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

4、a TM that recognizes S, then “P on ” leads to a contradiction. Crucial ingredient: 关键技术 Self-Reference: P accepts . 可计算理论5 What happens if a computer program M tries to answer questions about itself ? 程序自己分析自己的源程序会出什么结果？ Sometimes this is perfectly okay: - How big is ? - Is a proper TM? Other questi

5、ons lead to paradoxes:有时似是而非- Does halt or not?如停机 - Is there a smaller program M that is equivalent? 可计算理论6 What happens if a computer program M tries to answer questions about itself ? 程序自己分析自己的源程序会出什么结果？ Sometimes this is perfectly okay: - How big is ? - Is a proper TM? Other questions lead to pa

6、radoxes:有时似是而非- Does halt or not?如停机 - Is there a smaller program M that is equivalent? 可计算理论7 What happens if a computer program M tries to answer questions about itself ? 程序自己分析自己的源程序会出什么结果？ Sometimes this is perfectly okay: - How big is ? - Is a proper TM? Other questions lead to paradoxes:有时似是而非

7、- Does halt or not?如停机 - Is there a smaller program M that is equivalent? 可计算理论8 paradox 是错误理解的问题。 Maybe自引用的悖论原源自 TM 不能考 虑自己 is not able to consider itself? Question: How is it possible to have the structure: 1) Bla-bla-bla; 2) Look at M = ; 3) More Bla-bla-bla; 4) Do something weird M = How can we

8、have the complete description of M inside M itself? 1) Bla-bla-bla; 2) Look at M = ; 3) More Bla-bla-bla; 4) Do something weird M = 1) Bla-bla-bla; 2) Look at M = ; 3) More Bla-bla-bla; 4) Do something weird M = 可计算理论9 A paradox is a misunderstood problem. Maybe the paradoxes of self- references occ

9、ur because a TM is not able to consider itself? Question: How is it possible to have the structure: 1) Bla-bla-bla; 2) Look at M = ; 3) More Bla-bla-bla; 4) Do something weird M = How can we have the complete description of M inside M itself? 1) Bla-bla-bla; 2) Look at M = ; 3) More Bla-bla-bla; 4)

10、Do something weird M = 1) Bla-bla-bla;（平凡） 2) Look at M = ; 3) More Bla-bla-bla; 4) Do something weird(奇怪 动作） M = 在这里调用 自己 可计算理论10 n从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事,讲 的故事是：”从前有各庙，庙里有个老和尚，老和尚给小和 尚将故事,讲的什么故事是” Void story ( ) printf(“从前有个庙，庙里有个老和尚，老和尚给小和尚讲 故事,讲的故事是：”)； story( ); 毛病，没有递归深度控制，栈溢出时死机 镜子里面照镜子，电影里面

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

12、ry ( ) printf(“从前有个庙，庙里有个老和尚，老和尚给小和尚 讲故事,讲的故事是：”)； story( ); 毛病，没有递归深度控制，栈溢出时死机 镜子里面照镜子，电影里面放电影，故事里面讲故事, 庄生梦蝶，更新奇的是： 可计算理论13 It seems impossible to have a finite object that, as a part, has a complete description of itself. You expect a conflict between the finite amount of information-space and the

13、 infinite recursion. 注意这里递归 另例小学一年级语文数封面 可计算理论14 It seems impossible to have a finite object that, as a part, has a complete description of itself. You expect a conflict between the finite amount of information-space and the infinite recursion. 注意这里递归 另例小学一年级语文数封面 可计算理论15 On the other hand, we know

14、of many (mathematical) objects that have a finite description, yet appear to be infinitely detailed 分形 数学 可计算理论16 问题：自己调用自己的TM是否合法的图灵机 自己调用自己的程序是否合法的程序？ 本节要向证明， 满足一定规范非自己调用是合法的， 从数学本质上看，是正确的， 不是诡辩，不是悖论 而且用途广泛 . 可计算理论17 Attempt to describe a program that prints itself: M = print(“print(“print(“print

15、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 错误方法：Attempt to describe a program

16、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_(“_“):”) So it is possible to have such a TM M. The Recursion Theorem makes th

17、is explicit. 可计算理论19 The recursion theorem in CS shows how we can deal with the Droste/self-reference effect 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 const

18、ruct a program that prints itself且看 下面细细道来 可计算理论20 The recursion theorem in CS shows how we can deal with the Droste/self-reference effect 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

19、 smart 打印指定的串 （不难） How to construct a program that prints itself且看 下面细细道来 可计算理论21 Lemma C7.1 : Let w be an input 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

20、的TM Q (C程序)如下： Q(w ) char *p=q(w);/函数值是一个源程序串的指针 printf(p); 下页是书上的证明 可计算理论22 Lemma C7.1 : Let w be an input 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

21、 (C程序)如下： Q(w ) char *p=q(w);/函数值是一个源程序串的指针 printf(p); 下页是书上的证明 可计算理论23 Lemma C7.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)

22、 Output 可计算理论24 用C语言描述 库函数 B() Get_source_as( ,P)；/反编译 printf(“%s%s”,P,); main(char argv , int argc ) / 输入w 为 argv1=w char *A=;/B的源程序,如用argv0即EXE名,复制串 B(); 下页是书上的证明 输入TM , 输出：源程序串 可计算理论25 The SELF-program consists of two parts A and B: First part: A = P, so we will wait with this one B part (on inpu

23、t with M a TM subroutine): 1) Read , compute P % see Lemma 6.1 2) Use and P to print P M Now we know what P looks like. 可计算理论26 P 1) Given , compute P /反编译 2) Use and P to print P M After A-part on the tape: 1) Given . . . M B1 reads input on tape, computes P B2 prints: P 1) Given . . . M A = B1 = B

24、2 = B1,B2的串 可计算理论27 Instead of printing, a TM can do anything else with 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 every w*. (In

25、 the case of SELF, we had t(x,y) = x.) 可计算理论28 Instead of printing, a TM can do anything else with 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

26、) = t(,w) for every w*. (In the case of SELF, we had t(x,y) = x.) 可计算理论29 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(w) 加密 .，现在如下造程序R: R(w) char *s=; /R自己的 源程序或代码，前面已经证明

27、可得 s=s+w; /或用strcat T(S); 意义：R把自己的源程序作为处理的首部，当w=NULL时，R自 己处理自己（注意由于T是任何程序，例如是加密程序，则R把 自己加密） 下页是书上的证明 可计算理论30 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(w) 加密 .，现在如下造程序R:

28、 R(w) char *s=; /R自己的 源程序或代码，前面已经证明可得 s=s+w; /或用strcat T(S); 意义：R把自己的源程序作为处理的首部，当w=NULL时，R自 己处理自己（注意由于T是任何程序，例如是加密程序，则R把 自己加密） 下页是书上的证明 可计算理论31 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*.

29、 C描述的证明: 已经有了程序 T(w) 加密 .，现在如下造程序R: R(w) char *s=; /R自己的 源程序或代码，前面已经证明可得 s=s+w; /或用strcat T(S); 意义：R把自己的源程序作为处理的首部，当w=NULL时，R自 己处理自己（注意由于T是任何程序，例如是加密程序，则R把 自己加密） 下页是书上的证明 可计算理论32 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

30、be the TM that computes t. The TM R consists of 3 parts: A,B,T (input w): A = P B = Read input , print P M T = Calculate t on (tape content,w). 可计算理论33 The recursion theorem makes it clear that self- reference is possible for TMs: TM可自己调自己 is possible. It shows that programs like SELF are possible.

31、Makes undecidability proofs more transparent as they can now be phrased for a single TM. 1) Bla-bla-bla;平凡简单 2) Look at ; 3) More Bla-bla-bla; M = 可计算理论34 Proof by contradiction: 用C语言描述 设bool Deter_Accept(M ,w)是接受判定程序，造 TM B ( w)如 下： bool B ( w) printf (); /打印自己的源程序 OK = ! Deter_Accept(B,W); /递归 ret

32、urn OK /如果B接受w, OK=false, 则B不接受w, 下页是书上的证明 Theorem C7.3: The acceptance language ATM = | TM M accepts input w is undecidable. 接受问题是不可判定的 可计算理论35 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

33、); /递归 return OK /如果B接受w, OK=false, 则B不接受w,矛盾 下页是书上的证明 Theorem C7.3: The acceptance language ATM = | TM M accepts input w is undecidable. 接受问题是不可判定的 Deter_Accept(M,x) 对任何M,x都能判定 ，对特殊的M=B,x=w 当然也能 可计算理论36 Proof by contradiction:书上的证明 Assume that H decides ATM. Construct the following TM B (input w):

34、1) Print own description 2) 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 reply of B on will disagree. Contradiction. 可计算理论37 The previous proof gives a TM-computable counterexample for ev

35、ery H attempt. 用 自调用否定 导出矛盾 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 with a counterexample for H 可计算理论38 MINTM=|M是极小TM,等价TM中最短 定理C7.5 MINTM不可判定 自学。 可计算理论39 T

36、he 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 does not reject M. 与M的构造定义矛盾 与前几周证明的类似，这次更细致一些， 可计算理论59 把 M = (rejecting computing history

37、 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 does not reject M. 与M的构造定义矛盾 与前几周证明的类似，这次更细致一些， 可计算理论60 For any axiomatic description D

38、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 可计算理论62 Just as any mathematical theory, we can expand our Turing m

39、achine model for computation. We can ask the question: What can we compute with a Turing machine if (for some reason) we know the set ATM? Usually this is phrased in terms of an external oracle 喻示，圣贤 直观解释：有无穷个CPU的并行机 cp139 OS that answers questions “xS?” 可计算理论63 Just as any mathematical theory, we can expand our Turing machine model for computation. We can ask the question: What can we compute with a Turing machine if (for some reason) we know the set ATM? Usually this is phrased in terms of an external oracle 喻示，圣贤 直观解释：有无穷个CPU的并行机 cp139 OS t