1.10 Exercise 1.10

The following evaluations using the substitution model are tedious, and are sometimes simplified based on the results of earlier derivations, because the number of steps required to calculate this procedure grows very quickly.

First, (A 1 10). First, expanding the arguments to A until finding a base case:

Now, we know that (A 1 1) evaluates to 2. Building on this, (A 0 (A 1 1)) is the same as (A 0 2), which evaluates to (* 2 y), or 4 in this case. We could use this to substitute in values of calls of A until finding an answer, but the answer is simpler to find directly. Notice the following:

The answer is 2^10 = 1024

Next, (A 2 4). To solve this in fewer explicit steps, we use the result above and completely skip simple math procedures.

(A 2 4)

(A 1 (A 2 3))

(A 1 (A 1 (A 2 2)))

(A 1 (A 1 (A 1 (A 2 1))))

(A 2 1) = 2, so:

(A 1 (A 1 (A 1 2)))

(A 1 (A 1 (A 0 (A 1 1))))

(A 1 (A 1 (A 0 2)))

(A 1 (A 1 4))

This is a substitution we already know how to make. Accelerating the process:

Finally, (A 3 3)

In short, Ackermann’s function is very recursive. For the rest of the exercise, we consider procedures that evaluate A for fixed x values.

(define (f n) (A 0 n))

f evaluates a base case, with a result of 2 * n.

(define (g n) (A 1 n))

g generalizes the first expansion we did, which evaluates to 2 ^ n.

(define (h n) (A 2 n))

h generalizes the second expansion. Notice a few cases:

Put concisely, (h n) = 2^(h (dec n)).