Structure and Interpretation of Computer Programs gives this implementation of Ackermann's function:
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1) (A x (- y 1))))))
Exercise 1.10 asks for the "concise mathematical definitions" of the following functions that call A:
(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
The outputs of f and g for integers 1 - 4 are recognizable as 2n and 2^n. But h is 2^(2^n-1), a formula I could not recognize just by looking for a pattern in the outputs. How is one meant to complete this exercise? Is there a method for deriving the mathematical notation, perhaps based on the notation for Ackermann's function?
The book has already introduced the substitution method, so it's not wrong to use that.
Start with (A 0 n)
This is
(cond ((= n 0) 0)
((= 0 0) (* 2 n))
((= 0 1) 2)
(else (A (- 0 1) (A 0 (- n 1)))))
which is clearly 2n.
Next, (A 1 n) is
(cond ((= n 0) 0)
((= 1 0) (* 2 n))
((= n 1) 2)
(else (A (- 1 1) (A 1 (- n 1))))))
which is
(A 0 (A 1 (- n 1)))
or, taking advantage of the previous step,
(* 2 (A 1 (- n 1))
That is,
A 1 n = 2 * (A 1 (n-1))
= 2 * 2 * (A 1 (n-2))
= ...
Since we know that A x 1 = 2 for all x, we see that
A 1 n = 2 * 2 * ... * 2
with n factors, i.e. 2n.
Applying similar reasoning to the last case left as an exercise.