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 #
