Exercise 1.10 of SICP « Dan's Thoughts

26May/090

Exercise 1.10 of 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))))))

What are the values of the following expressions?

> (A 1 10)
1024
> (A 2 4)
65536
> (A 3 3)
65536

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 5n²

(define (f n) (A 0 n))
$f(n) = 2n$
(define (g n) (A 1 n))
(g 3)
(A 1 3)
(A 0 (A 1 2))
(* 2 (A 0 (A 1 1)))
(* 2 (* 2 2)
8
$g(n) = 2^n$
(define (h n) (A 2 n))
(h 3)
(A 2 3)
(A 1 (A 2 2))
From the previous result I know that (h 3) will look like $2^{A(2,2)}$
(A 2 2)
(A 1 (A 2 1))
From the previous result I know that (h 2) will look like $2^{A(2,1)}$
$h(3) = 2^{2^{A(2,1)}} = 2^{2^2}$
$h(n) = 2^{2^{\cdot^{\cdot^{2^2}}}}$
Where the exponent repeats n times.
This operation is called tetration.
(define (k n) (* 5 n n))
$f(n) = 5n^2$