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 2^{10}.

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 2^{16}, 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, 2^{16}.

### (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.