SICP Exercise 1.10

Question

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 $5n^2$.

Answer

The first part of this is easy to answer since we can just run the commands and see the outputs.

(A 1 10)
; returns 1024
(A 2 4)
; returns 65536
(A 3 3)
; returns 65536

As we see, the final two operations return the same result: 65536. Another thing that may jump out is that all the results of the three operations are powers of 2: $2^{10}$, $2^{16}$, and $2^{16}$, respectively.

So, let us turn to the more difficult second part of the question.

The procedure f is quite straightforward: since the conditional (= x 0) is always fulfilled in this case, the result of this will always be (* 2 n).

Next, let us take a look at procedure g. The easiest way to understand what this does is to step through a sample evaluation sequence. Let us use 5 as a value for n.

(A 1 5)
(A (- 1 1) (A 1 (- 5 1)))
(A 0 (A 1 4))
; the (= x 0) conditional is met
(* 2 (A 1 4))
(* 2 (A (- 1 1) (- 4 1)))
(* 2 (A 0 (A 1 3)))
(* 2 (* 2 (A 1 3)))
(* 2 (* 2 (A (- 1 1) (A 1 (- 3 1)))))
(* 2 (* 2 (A 0 (A 1 2))))
(* 2 (* 2 (* 2 (A 1 2))))
(* 2 (* 2 (* 2 (A (- 1 1) (A 1 (- 2 1))))))
(* 2 (* 2 (* 2 (A 0 (A 1 1)))))
(* 2 (* 2 (* 2 (* 2 (A 1 1)))))
; the (= y 1) conditional is met
(* 2 (* 2 (* 2 (* 2 2))))
(* 2 (* 2 (* 2 4)))
(* 2 (* 2 8))
(* 2 16)
32

Of course, this is nothing other than $2^n$. In this case, n is equivalent to 5, so the result is $2^5$ or 32.

How about procedure h? Let us again use the substitution model to track the evaluation using the value 3 for n:

(A 2 3)
(A (- 2 1) (A 2 (- 3 1)))
(A 1 (A 2 2))
(A 1 (A (- 2 1) (A 2 (- 2 1))))
(A 1 (A 1 (A 2 1)))
; the (= y 1) conditional is met
(A 1 (A 1 2))
(A 1 (A (- 1 1) (A 1 (- 2 1))))
(A 1 (A 0 (A 1 1)))
; the (= y 1) conditional is met
(A 1 (A 0 2))
; the (= x 0) conditional is met
(A 1 (* 2 2))
(A 1 4)
; substitute g function expression (2^y)
16

So (A 2 3) simply returns (A 1 4). But we already know what (A 1 4) does, as it’s the same form we saw in g. The result of this equation should therefore be $2^4$ or 16.

But what does the function actually do? If we take the procedure evaluation above apart, we will find that h returns the square of the result of its previous iteration, starting with the value 2.

So, to sum it up, here are the three function definitions: $$f(x)=2x$$ $$g(x)=2^x$$ $$h(x)=2^{h(x-1)}$$

A little footnote: These are not to be understood as function definitions in the strict mathematical sense, but rather as descriptions of how the procedures behave. x here describes only positive integers, and there are some edge cases such as (g 0) evaluating to 0 rather than to 1 (as $2^0$ should).