  ## 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 is 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  #

```