SICP Exercise 1.10

Exercise1-10.md

The following are the results from defining and evaluating the Ackermann's function on various arguments.

(define (A x y)
  (cond ((= y 0) 0)
  	((= x 0) (* 2 y))
	((= y 1) 2)
	(else (A (- x 1)
	      	 (A x (- y 1))))))
; A

(A 1 10)
; 1024

(A 2 4)
; 65536

(A 3 3)
; 65536

Mathematical definition of (A 0 n)

Let us evaluate (A 0 n) for various arguments

(define (f n) (A 0 n))
; f

(f 0)
; 0

(f 1)
; 2

(f 2)
; 4

(f 3)
; 6

(f 4)
; 8

(f 5)
; 10

As can be seen, (f n) evaluates to 2n. As we run through the function definition, when (= x 0) evaluates to true, the Ackermann's function evaluates to (* 2 y) which is the value we see.

Mathematical definition of (A 1 n)

Let us evaluate (A 1 n) for various arguments

(define (g n) (A 1 n))
; g

(g 0)
; 0

(g 1)
; 2

(g 2)
; 4

(g 3)
; 8

(g 4)
; 16

(g 5)
; 32

As can be seen, with the exception of when n is 0, (g n) evaluates to . To see why this is the case, we run through the Ackermann's function definition.

(A 1 n)
(A (- 1 1) (A (1 (- n 1))))
(A 0 (A (1 (- n 1))))
(* 2 A(1 (- n 1)))

...

The evaluation expands till the terminal case (= n 1) which evaluates to 2. Thus, we multiply 2 with itself n times to get

Mathematical definition of (A 2 n)

Evaluating (A 2 n) for various arguments, we get

(define (h n) (A 2 n))
; h

(h 0)
; 0

(h 1)
; 2

(h 2)
; 4

(h 3)
; 16

(h 4)
; 65536

Its not clear what is going on immediately. But the expansion of evaluation gives us a clue,

(A 2 n)
(A (- 2 1) (A (2 (- n 1))))
(A 1 (A (2 (- n 1))))

...

We get . Expanding down to the terminal case of (= n 1), we see that 2 is powered with itself n times. This can also be written using [Knuth's up-arraw notation] (http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation) as ![equation3] (http://www.sciweavers.org/upload/Tex2Img_1405289780/render.png).