SICP exercise 1.10

From Drewiki

Jump to: navigation, search

The following procedure computes a mathematical function called Ackermann's function:

 

The exercise has two parts.

Contents

Problem A.

What are the values of the following expressions?

 

Solution A.

Easy; just type the expressions into the Scheme interpreter.

 

Output:

1024


 

Output:

65536


 

Output:

65536

Problem B.

Consider the following procedures, where A is the procedure defined above:

 

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.

Solution B.

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

 

Output:

0


 

Output:

2


 

Output:

4


 

Output:

6


 

Output:

8


 

Output:

20


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

 

Output:

0
 

Output:

2
 

Output:

8
 

Output:

16
 

Output:

1024

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

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

 

Output:

0
 

Output:

2
 

Output:

4
 

Output:

16
 

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.

 

Output:

+inf

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

 

And now (h 3) by substitution:

 

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

 

reduces to

 

We know that the value of

 

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

 

Also,

 

is the terminating case for

 

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

 

which reduces to

 

which is 22 or 4. The parent of

 

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

 

whose value is 2^4 or 16.

The pattern, then, is

2^{2^{2^{.^{.^{.^{2}}}}}}

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

2^{2^{2^{2^{2}}}}

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

Personal tools