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

From Drewiki
Jump to: navigation, search

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

Personal tools