home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / alt / folklore / computer / 16658 < prev    next >
Encoding:
Internet Message Format  |  1992-11-23  |  2.1 KB
  1. Path: sparky!uunet!olivea!gossip.pyramid.com!pyramid!oracle!unrepliable!bounce
  2. From: ken@us.oracle.com (Ken C. Stewart)
  3. Newsgroups: alt.folklore.computers
  4. Subject: Ackermann's function
  5. Summary: Ackermann's function, and why the vi macros are better than FORTRAN ...
  6. Keywords: Ackermann's function, recursion, primitive-recursive, FORTRAN, COBOL
  7. Message-ID: <ken.722284796@base>
  8. Date: 20 Nov 92 18:39:56 GMT
  9. Sender: usenet@oracle.us.oracle.com (Oracle News Poster)
  10. Organization: Oracle Corp., Redwood Shores CA
  11. Lines: 26
  12. Nntp-Posting-Host: base.us.oracle.com
  13. X-Disclaimer: This message was written by an unauthenticated user
  14.               at Oracle Corporation.  The opinions expressed are those
  15.               of the user and not necessarily those of Oracle.
  16.  
  17. Can anyone remind me (ahem) of the definition of Ackermann's function (a pair
  18. of mutually-recursive functions I think?)?  I saw it on the 'net years ago
  19. that it was one of the simpler examples of a recursive function that was not
  20. "primitive recursive", meaning, I think, that it could not be evaluated
  21. by iterative means, as the terminating condition for the loop to evaluate it
  22. depended on evaluating Ackermann's function ... I also seem to remember that
  23. since it required the programming language it was expressed in to support
  24. recursion, and since COBOL and FORTRAN (or at least some standard flavour
  25. thereof) don't, that COBOL and FORTRAN are not general purpose programming
  26. languages, whereas, say, vi macros are (see articles passim concerning
  27. Universal Turing Machine simulation using vi macros).
  28.  
  29. Anyway, could some kind soul please post it, and explain what kind of
  30. recursion it embodies if not "primitive recursion"?
  31.  
  32. Thanks!
  33.  
  34. Ken Stewart,                    Telephone:   (301) 907 2225
  35. Technical Consultant,           Fax:         (301) 657 0037
  36. Oracle Federal,                 Oracle*Mail: kstewart.us
  37. Bethesda, MD 20814              Internet:    kstewart@us.oracle.com
  38. --
  39. Ken Stewart,                  Telephone:   (301) 907 2225
  40. Technical Consultant,         Fax:         (301) 657 0037
  41. Oracle Federal,                Oracle*Mail: kstewart.us
  42. Bethesda, MD 20814              Internet:    kstewart@us.oracle.com
  43.