## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

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

The exercise has two parts.

## Contents |

## 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 <math>5n^2</math>.

## Solution B.

It's relatively easy to see from the definition of `A` that `(f n)` computes <math>2n</math>. 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 <math>2^n</math> for <math>n>0</math>, 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 <math>2^m</math> 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 <math>2^2</math> 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

<math>2^{2^{2^{.^{.^{.^{2}}}}}}</math>

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

<math>2^{2^{2^{2^{2}}}}</math>

The next value, `(h 5)`, is <math>2^{65536}</math>, which is an extremely large number
(too large for Chicken Scheme 2.6 to calculate with "standard" integers).