A(x, 1, 1) = S(x) A(x, S(y), 1) = S(A(x, y, 1)) A(x, 1, S(z)) = x A(x, S(y), S(z)) = A(x, A(x, y, S(z)), z)For instance A(x, y, 1) = x+y; A(x, y, 2) = x*y; A(x, y, 3) = x

Note that:

A(x, 1, 2) = x A(x, S(y), 2) = S(x, A(x, y, 2), 1) A(x, 1, 3) = x A(x, S(y), 3) = S(x, A(x, y, 3), 2)For positive integer arguments A always terminates but A(x, x, x) grows faster than any primitive recursive function and may be easier to understand than the simpler Ackermanâ€™s function.

In Scheme:

(define (S x) (+ x 1)) (define (A x y z) (if (= 1 z) (if (= 1 y) (S x) (S (A x (- y 1) 1))) (if (= 1 y) x (A x (A x (- y 1) z) (- z 1)))))Beware that execution time is proportional to value of A.