home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 12925 < prev    next >
Encoding:
Text File  |  1992-10-09  |  1.4 KB  |  36 lines

  1. Newsgroups: sci.math
  2. Path: sparky!uunet!pmafire!mica.inel.gov!guinness!opal.idbsu.edu!holmes
  3. From: holmes@opal.idbsu.edu (Randall Holmes)
  4. Subject: Re: help with recursive functions
  5. Message-ID: <1992Oct8.183408.5402@guinness.idbsu.edu>
  6. Sender: usenet@guinness.idbsu.edu (Usenet News mail)
  7. Nntp-Posting-Host: opal
  8. Organization: Boise State University
  9. References: <1b074cINN4fu@usenet.INS.CWRU.Edu>
  10. Date: Thu, 8 Oct 1992 18:34:08 GMT
  11. Lines: 23
  12.  
  13. In article <1b074cINN4fu@usenet.INS.CWRU.Edu> cxm7@po.CWRU.Edu (Colin Mclarty) writes:
  14. >
  15. >    I'd like some help with partial recursive functions which
  16. >do not extend to (total) recursive ones.  I can prove there is no
  17. >effective routine for extending all partials to total recursive
  18. >functions, but I do not see how to prove there are particular
  19. >partial recursive functions that do not extend to recursive.  Are
  20. >there typical methods from proving this in particular cases?
  21. >
  22. >Colin McLarty
  23.  
  24. Easy example:  the function which, given the code for a Turing
  25. machine, simulates its operation and outputs the number of steps it
  26. takes to halt if it does halt.  If this function could be extended to
  27. a total recurisive function, it could be used immediately to solve the
  28. halting problem.
  29.  
  30.  
  31. -- 
  32. The opinions expressed        |     --Sincerely,
  33. above are not the "official"    |     M. Randall Holmes
  34. opinions of any person        |     Math. Dept., Boise State Univ.
  35. or institution.            |     holmes@opal.idbsu.edu
  36.