SICP exercise 1.10
From Drewiki
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
We can verify this by confirming that the value of (h 4) is 65536, which is
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).
