home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 12887 < prev    next >
Encoding:
Text File  |  1992-10-07  |  1.4 KB  |  35 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
  3. From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
  4. Subject: Re: help with recursive functions
  5. Message-ID: <1992Oct8.052110.23092@CSD-NewsHost.Stanford.EDU>
  6. Sender: news@CSD-NewsHost.Stanford.EDU
  7. Organization: Computer Science Department,  Stanford University.
  8. References: <1b074cINN4fu@usenet.INS.CWRU.Edu>
  9. Date: Thu, 8 Oct 1992 05:21:10 GMT
  10. Lines: 23
  11.  
  12. In article <1b074cINN4fu@usenet.INS.CWRU.Edu> cxm7@po.CWRU.Edu (Colin Mclarty) writes:
  13. >
  14. >    I'd like some help with partial recursive functions which
  15. >do not extend to (total) recursive ones.  I can prove there is no
  16. >effective routine for extending all partials to total recursive
  17. >functions, but I do not see how to prove there are particular
  18. >partial recursive functions that do not extend to recursive.  Are
  19. >there typical methods from proving this in particular cases?
  20. >
  21. >Colin McLarty
  22.  
  23.  
  24. Rogers, Chapter 2, Theorem II: There exists p.r. \psi with no recursive
  25. extension.
  26.  
  27. Proof.  Take \psi(x) = \phi_x(x)+1, and let \phi_y be any recursive
  28. extension of \psi.  Since \phi_y is recursive, \psi(y) halts, whence
  29. \phi_y(y) = \phi_y(y)+1.
  30.  
  31. -- 
  32. =================================================== In short, I am floundering
  33. Vaughan Pratt   pratt@cs.Stanford.EDU  415-494-2545 around and don't take what
  34. =================================================== I say seriously.
  35.