home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / alt / folklore / computer / 16689 < prev    next >
Encoding:
Text File  |  1992-11-23  |  2.8 KB  |  103 lines
  1. Newsgroups: alt.folklore.computers
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!spool.mu.edu!umn.edu!sctc.com!boebert
  3. From: boebert@sctc.com (Earl Boebert)
  4. Subject: Re: Ackermann's function
  5. Message-ID: <1992Nov23.211817.22693@sctc.com>
  6. Keywords: Ackermann's function, recursion, primitive-recursive, FORTRAN, COBOL
  7. Organization: SCTC
  8. References: <ken.722284796@base> <1992Nov23.193734.253@cs.cornell.edu>
  9. Date: Mon, 23 Nov 1992 21:18:17 GMT
  10. Lines: 91
  11.  
  12. chapman@cs.cornell.edu (Richard Chapman) writes:
  13.  
  14. >ken@us.oracle.com (Ken C. Stewart) writes:
  15.  
  16. >>Can anyone remind me (ahem) of the definition of Ackermann's function (a pair
  17. >>of mutually-recursive functions I think?)?  
  18.  
  19. >The Ackermann function: 
  20.  
  21. >    f(0,y)  = y + 1
  22. >    f(x+1,0) = f(x,1)
  23. >    f(x+1,y+1) = f(x,f(x+1,y))
  24.  
  25. [exchange on recursion deleted]
  26.  
  27. >While recursion is not allowed in FORTRAN, you can implement it
  28. >yourself in a FORTRAN program by explicitly implementing a stack and
  29. >handling it all yourself. Now, whether or not FORTRAN has recursion
  30. >has little to do with the expressive power of the language; since
  31. >on-line storage and memory are finite, the most you can implement in
  32. >any language on any computer is a function that could be implemented by
  33. >a finite-state automaton (which is a far smaller class than the Turing
  34. >computable functions). However, barring the finite memory limit. If
  35. >you assume you have infinite memory size, and each location can hold
  36. >an arbitrarily large integer, all you need to implement all the
  37. >computable functions are: load a memory location with zero, increment
  38. >contents of a memory location, conditional jump, and transfer contents of one
  39. >memory location to another. All these are operations which FORTRAN and
  40. >COBOL are both capable of.
  41.  
  42.  
  43. From CACM 8:2, February 1965:
  44.  
  45.  
  46. INTEGER FUNCTION ACKER(M,N)
  47.  
  48. C COMPUTE ACKERMANN'S FUNCTION, DEFINED BY
  49. C ACKER(0,N) = N+1
  50. C ACKER(M+1,0) = ACKER(M,1)
  51. C ACKER(M+1,N+1) = ACKER(M,(ACKER(M+1,N))
  52. C SIZE OF VALUE AND PLACE TABLES IS ONE MORE THAN LARGEST M EXPECTED
  53.  
  54. INTEGER VALUE(6), PLACE(6)
  55.  
  56. C TEST FOR ZERO M
  57.  
  58. IF (M .NE. 0) GO TO 1
  59. ACKER = N+1
  60. RETURN
  61.  
  62. C NON-ZERO M, INITIALIZE FOR ITERATION
  63.  
  64. 1 VALUE = 1
  65. PLACE = 0
  66.  
  67. C ITERATION LOOP, GET NEW VALUE
  68.  
  69. 2 VALUE = VALUE+1
  70. PLACE = PLACE+1
  71.  
  72. C PROPAGATE VALUE
  73.  
  74. DO 4 I=1,M
  75. IF (PLACE(I) .NE. 1) GO TO 3
  76.  
  77. C INITIATE NEW LEVEL
  78.  
  79. VALUE(I+1) = VALUE
  80. PLACE(I+1) = 0
  81. IF (I .EQ. M) GO TO 5
  82. GO TO 2
  83.  
  84. 3 IF (PLACE(I+1) .NE VALUE(I+1)) GO TO 2
  85. VALUE(I+1) = VALUE
  86.  
  87. 4 PLACE(I+1) = PLACE(I+1)+1
  88.  
  89. C CHECK FOR END OF ITERATION
  90.  
  91. 5 IF (PLACE(M+1) .NE. N) GO TO 2
  92. ACKER = VALUE
  93. RETURN
  94. END
  95.  
  96. Written by H. Gordon Rice, one of the founders of Computer Sciences
  97. Corp. He noted with satisfaction that computing ACKER (5,0) = 65,533
  98. required less than 10 seconds on a Univac 1107.  And yes, people used
  99. to write stuff like that above for a living :-)
  100.  
  101. Earl
  102.  
  103.