1.10.md

1.10

Question

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)

(A 2 4)

(A 3 3)

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 $5n^2$.

Answer

1 ]=> (A 1 10)

;Value: 1024 ; Looks like 2^10

1 ]=> (A 2 4)

;Value: 65536 ; 2^2^2^2

1 ]=> (A 3 3)

;Value: 65536 ; Non-analytic

Expression	Function
(A 0 n)	$f(n) = 2 * n$
(A 1 n)	$f(n) = 2^n$
(A 2 n)	$f(n) = ((2^2)^2 \cdots)^2$ n times

Ackerman's function illustrates the power (and obscurity) of recursive programming: distributing state across deferred computational chain allows the programmer to compactly describe processes that lack analytic form ((A 3 n) onward).