SICP exercise 1.10

From Drewiki

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))))))

The exercise has two parts.

Problem A.

What are the values of the following expressions?

(A 1 10)
 
(A 2 4)
 
(A 3 3)

Solution A.

Easy; just type the expressions into the Scheme interpreter.

(A 1 10)

Output:

1024

(A 2 4)

Output:

65536

(A 3 3)

Output:

65536

Problem B.

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².

Solution B.

It's relatively easy to see from the definition of A that (f n) computes 2n. Examples:

(f 0)

Output:

0

(f 1)

Output:

2

(f 2)

Output:

4

(f 3)

Output:

6

(f 4)

Output:

8

(f 10)

Output:

20

The function computed by g isn't obvious at first glance. Let's try a few combinations:

(g 0)

Output:

0

(g 1)

Output:

2

(g 3)

Output:

8

(g 4)

Output:

16

(g 10)

Output:

1024

It looks like (g n) is 2ⁿ for n > 0, 0 otherwise.

The function computed by h isn't obvious, either. More tests:

(h 0)

Output:

0

(h 1)

Output:

2

(h 2)

Output:

4

(h 3)

Output:

16

(h 4)

Output:

65536

On Chicken v2.6 on a MacBook Pro running Mac OS X 10.5, the combination (h 5) evaluates to +inf, which means infinity, i.e., the result has exceeded the computer's numeric range.

(h 5)

Output:

+inf

It's still not apparent what function procedure h computes. Let's evaluate (h 2) by substitution:

(h 2)
(A 2 2)
(A 1 (A 2 1))
(A 1 2)
(A 0 (A 1 1))
(A 0 2)
(* 2 2)
4

And now (h 3) by substitution:

(h 3)
(A 2 3)
(A 1 (A 2 2))
(A 1 (A 1 (A 2 1)))
(A 1 (A 1 2))
(A 1 (A 0 (A 1 1)))
(A 1 (A 0 2))
(A 1 (* 2 2))
(A 1 4)
(A 0 (A 1 3))
(A 0 (A 0 (A 1 2)))
(A 0 (A 0 (A 0 (A 1 1))))
(A 0 (A 0 (A 0 2)))
(A 0 (A 0 (* 2 2)))
(A 0 (A 0 4))
(A 0 (* 2 4))
(A 0 8)
(* 2 8)
16

Note that in the evaluation of (h 3) by substitution,

(A 2 n)

reduces to

(A 1 (A 2 (- n 1)))

We know that the value of

(A 1 m)

is 2^m from our earlier analysis of procedure g, where m is the value of the combination

(A 2 (- n 1))

Also,

(A 2 1)

is the terminating case for

(A 2 n)

which produces a value of 2. Its parent (caller) is

(A 1 (A 2 1))

which reduces to

(A 1 2)

which is 2² or 4. The parent of

(A 1 (A 2 1))

is (A 2 2), so its value is also 4. The parent of that node is

(A 1 (A 2 2))

whose value is 2^4 or 16.

The pattern, then, is

We can verify this by confirming that the value of (h 4) is 65536, which is

The next value, (h 5), is 2⁶⁵⁵³⁶, which is an extremely large number (too large for Chicken Scheme 2.6 to calculate with "standard" integers).