.

Exercise 1.10. The following procedure computes a mathematical function called 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))))))
``````

What are the values of the following expressions?

``````(A 1 10)

(A 2 4)

(A 3 3)
``````

Consider the following procedures, where A is the procedure defined above:

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

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

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

(define (k n) (* 5 n n))
``````

Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n. For example, (k n) computes 5n2.

### (A 1 10)

``````(A 1 10)
= (A 0 (A 1 9))
= (A 0 (A 0 (A 1 8)))
= (A 0 (A 0 (A 0 (A 1 7))))
... this will continue on until
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
``````

Since `(A 1 1)` is 2 (from the third line of the `cond`), this is `(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))`.

Then each of those instances of `(A 0 y)` evaluate to `(* 2 y)` and the result is 210.

We can see that `(A 1 n)` is 2`n`, for any positive integer `n` (see the procedure `g` below). We will use this in calculating `(A 2 4)` below.

### (A 2 4)

``````(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 1 (A 1 (A 1 2))) ; using the third line of the `cond`
= (A 1 (A 1 4)) ; using the general result from the previous example
= (A 1 16) ; again using the general result from the previous example
``````

which is 216, once more using the general result from the previous example.

### (A 3 3)

``````(A 3 3)
= (A 2 (A 3 2))
= (A 2 (A 2 (A 3 1)))
= (A 2 (A 2 2))
= (A 2 (A 1 (A 2 1)))
= (A 2 (A 1 2))
= (A 2 4)
``````

This is the same as the previous example, 216.

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

`(f n)` = `(A 0 n)` = `(* 2 n)` for any positive integer `n`.

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

See the expansion of `(A 1 10)` above. `(g n)` is `(A 1 n)`, which is 2`n`, for any positive integer `n`.

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

`(h n) = (A 2 n) = (A 1 (A 2 (- n 1)))`. This is the same as `(g (A 2 (- n 1)))`, or `(g (h (- n 1)))`.

Another way to write this is 2`(h (- n 1))`.

This is 2 to the power of 2 to the power of 2 to the power of… 2, with a total of `n` - 1 twos.