Exercise 1.10

The 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\) .

The Answer

Evaluating the expressions

Let us first define A again:

(require racket/trace)

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

(trace A)

Now evaluating:

(A 1 10)
>(A 1 10)
> (A 1 9)
> >(A 1 8)
> > (A 1 7)
> > >(A 1 6)
> > > (A 1 5)
> > > >(A 1 4)
> > > > (A 1 3)
> > > > >(A 1 2)
> > > > > (A 1 1)
< < < < < 2
> > > > >(A 0 2)
< < < < <4
> > > > (A 0 4)
< < < < 8
> > > >(A 0 8)
< < < <16
> > > (A 0 16)
< < < 32
> > >(A 0 32)
< < <64
> > (A 0 64)
< < 128
> >(A 0 128)
< <256
> (A 0 256)
< 512
>(A 0 512)
<1024

The trace doesn't give us the picture as whole, unlike the substitution model. A calls itself twice in the else clause. Once as a tail-call and once as parameter to the tail-call. As the chain expands (represented by > in the trace), we see these inner calls. Once the innermost call is evaluated, and a value is achieved (represented by < in the trace) we start to see values of the inner calls become substituted in the outer calls.

Similarly:

(A 2 4)
>(A 2 4)
> (A 2 3)
> >(A 2 2)
> > (A 2 1)
< < 2
> >(A 1 2)
> > (A 1 1)
< < 2
> >(A 0 2)
< <4
> (A 1 4)
> >(A 1 3)
> > (A 1 2)
> > >(A 1 1)
< < <2
> > (A 0 2)
< < 4
> >(A 0 4)
< <8
> (A 0 8)
< 16
>(A 1 16)
> (A 1 15)
> >(A 1 14)
> > (A 1 13)
> > >(A 1 12)
> > > (A 1 11)
> > > >(A 1 10)
> > > > (A 1 9)
> > > > >(A 1 8)
> > > > > (A 1 7)
> > > >[10] (A 1 6)
> > > >[11] (A 1 5)
> > > >[12] (A 1 4)
> > > >[13] (A 1 3)
> > > >[14] (A 1 2)
> > > >[15] (A 1 1)
< < < <[15] 2
> > > >[14] (A 0 2)
< < < <[14] 4
> > > >[13] (A 0 4)
< < < <[13] 8
> > > >[12] (A 0 8)
< < < <[12] 16
> > > >[11] (A 0 16)
< < < <[11] 32
> > > >[10] (A 0 32)
< < < <[10] 64
> > > > > (A 0 64)
< < < < < 128
> > > > >(A 0 128)
< < < < <256
> > > > (A 0 256)
< < < < 512
> > > >(A 0 512)
< < < <1024
> > > (A 0 1024)
< < < 2048
> > >(A 0 2048)
< < <4096
> > (A 0 4096)
< < 8192
> >(A 0 8192)
< <16384
> (A 0 16384)
< 32768
>(A 0 32768)
<65536

(A 3 3)
>(A 3 3)
> (A 3 2)
> >(A 3 1)
< <2
> (A 2 2)
> >(A 2 1)
< <2
> (A 1 2)
> >(A 1 1)
< <2
> (A 0 2)
< 4
>(A 2 4)
> (A 2 3)
> >(A 2 2)
> > (A 2 1)
< < 2
> >(A 1 2)
> > (A 1 1)
< < 2
> >(A 0 2)
< <4
> (A 1 4)
> >(A 1 3)
> > (A 1 2)
> > >(A 1 1)
< < <2
> > (A 0 2)
< < 4
> >(A 0 4)
< <8
> (A 0 8)
< 16
>(A 1 16)
> (A 1 15)
> >(A 1 14)
> > (A 1 13)
> > >(A 1 12)
> > > (A 1 11)
> > > >(A 1 10)
> > > > (A 1 9)
> > > > >(A 1 8)
> > > > > (A 1 7)
> > > >[10] (A 1 6)
> > > >[11] (A 1 5)
> > > >[12] (A 1 4)
> > > >[13] (A 1 3)
> > > >[14] (A 1 2)
> > > >[15] (A 1 1)
< < < <[15] 2
> > > >[14] (A 0 2)
< < < <[14] 4
> > > >[13] (A 0 4)
< < < <[13] 8
> > > >[12] (A 0 8)
< < < <[12] 16
> > > >[11] (A 0 16)
< < < <[11] 32
> > > >[10] (A 0 32)
< < < <[10] 64
> > > > > (A 0 64)
< < < < < 128
> > > > >(A 0 128)
< < < < <256
> > > > (A 0 256)
< < < < 512
> > > >(A 0 512)
< < < <1024
> > > (A 0 1024)
< < < 2048
> > >(A 0 2048)
< < <4096
> > (A 0 4096)
< < 8192
> >(A 0 8192)
< <16384
> (A 0 16384)
< 32768
>(A 0 32768)
<65536

As you can see the behaviour of Ackermann's function is quite erratic.

Defining the functions

Turning our attention to the single-arity procedures given above.

(f n)

(define (f n) (A 0 n))
(trace f)

This function directly evaluates to the second clause of A, and doubles y:

(f 2)
>(f 2)
>(A 0 2)
<4

(f 3)
>(f 3)
>(A 0 3)
<6

Therefore it can be defined as:

\[f(n) = 2n\]

(g n)

(define (g n) (A 1 n))
(trace g)

This function simplifies into (A 0 (A 1 (- n 1))). The outer call simplifies into (* 2 (A 1 (- n 1))). Thus, each call to (g n) is just double of (g (- n 1)), until the base case of (g 1) (i.e. (A 1 1)) is reached, whereby the value 2 is substituted. This is equivalent to:

(define (g n)
  (if (= n 1)
      2
      (* 2 (g (- n 1)))))

Therefore, \(2\) is just multiplied \(n\) times:

(g 4)
>(g 4)
>(A 1 4)
> (A 1 3)
> >(A 1 2)
> > (A 1 1)
< < 2
> >(A 0 2)
< <4
> (A 0 4)
< 8
>(A 0 8)
<16

(g 6)
>(g 6)
>(A 1 6)
> (A 1 5)
> >(A 1 4)
> > (A 1 3)
> > >(A 1 2)
> > > (A 1 1)
< < < 2
> > >(A 0 2)
< < <4
> > (A 0 4)
< < 8
> >(A 0 8)
< <16
> (A 0 16)
< 32
>(A 0 32)
<64

We can define \(g(n)\) as:

\[g(n) = 2^n\]

(h n)

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

We can simplify (h n) in terms of (g n) and itself:

(define (h n)
  (if (= n 1)
      2
      (g (h (- n 1)))))

This means (g n) is chained till \(n\) equal \(1\). In other words, \(2\) is repeatedly exponentiated (i.e. tetrated) \(n\) times:

(h 1)
2

(h 2)
4

(h 3)
16

Using Knuth's up arrow notation, we can define \(h(n)\) as:

\[h(n) = 2 \uparrow\uparrow n\]

Comments