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 twoargument 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 #
© 20022024 J.M. van der Veer (jmvdveer@xs4all.nl)
