Algol 68 Genie

ackermann.a68

     
   1  #
   2   
   3  @section Synopsis
   4  
   5  Ackermann function, a paradigm total computable function that is not primitive recursive. 
   6  
   7  All primitive recursive functions (that can also be computed iteratively) are total and 
   8  computable, but not all total computable functions are primitive recursive.
   9  
  10  This two-argument A(m, n) version by Péter and Robinson (commonly called "the" Ackermann
  11  function) is a paradigm total computable function that is not primitive recursive. 
  12  
  13  The function f(n) = A(n, n) grows faster than any primitive recursive function, including 
  14  the exponential function, the factorial function, and multi- and superfactorial functions.
  15  
  16  The extremely deep recursion of this function is commonly used in testing programming language
  17  implementations.
  18  
  19  #
  20  
  21  PROC ack = (INT m, n) INT:
  22       IF m = 0
  23       THEN n + 1
  24       ELSE (n = 0 | ack (m - 1, 1) | ack (m - 1, ack (m, n - 1)))
  25       FI;
  26  
  27  PROC f = (INT n) INT: ack (n, n);
  28  
  29  FOR m TO 3 
  30  DO print (("f(", whole (m, 0), ") = ", whole (f (m), 0), newline));
  31     FOR n TO m 
  32     DO print (("A(", whole (m, 0), ", ", whole (n, 0), ") = ", whole (ack (m, n), 0), newline))
  33     OD
  34  OD
  35  
  36  #
  37  Output:
  38  f(1) = 3
  39  A(1, 1) = 3
  40  f(2) = 7
  41  A(2, 1) = 5
  42  A(2, 2) = 7
  43  f(3) = 61
  44  A(3, 1) = 13
  45  A(3, 2) = 29
  46  A(3, 3) = 61
  47  #
Deze website is gearchiveerd door de KB, nationale bibliotheek.

This website is archived by the National Library of the Netherlands.