2011-08-30

SICP Exercise 1.10: Ackermann's Function

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 5n2.

Ah, more substitution! What joy!
  (A 1 10)
= (A (- 1 1) (A 1 (- 10 1)))
= (A 0 (A 1 9))
= (A 0 (A (- 1 1) (A 1 (- 9 1))))
= (A 0 (A 0 (A 1 8)))
= (A 0 (A 0 (A (- 1 1) (A 1 (- 8 1)))))
= (A 0 (A 0 (A 0 (A 1 7))))
= (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 7 1))))))
= (A 0 (A 0 (A 0 (A 0 (A 1 6)))))
= (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 6 1)))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 5 1))))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 4 1)))))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 3 1))))))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 2 1)))))))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 2)))))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 4))))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 8)))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 16))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 32)))))
= (A 0 (A 0 (A 0 (A 0 (* 2 32)))))
= (A 0 (A 0 (A 0 (A 0 64))))
= (A 0 (A 0 (A 0 (* 2 64))))
= (A 0 (A 0 (A 0 128)))
= (A 0 (A 0 (* 2 128)))
= (A 0 (A 0 256))
= (A 0 (A 0 256))
= (A 0 (* 2 256))
= (A 0 512)
= (* 2 512)
= 1024
Now let's remember that (A 1 10) evaluates to 1024. It'll come in handy in a minute!
  (A 2 4)
= (A (- 2 1) (A 2 (- 4 1))
= (A 1 (A 2 3))
= (A 1 (A (- 2 1) (A 2 (- 3 1))))
= (A 1 (A 1 (A 2 2)))
= (A 1 (A 1 (A (- 2 1) (A 2 (- 2 1)))))
= (A 1 (A 1 (A 1 (A 2 1))))
= (A 1 (A 1 (A 1 2)))
= (A 1 (A 1 (A (- 1 1) (A 1 (- 2 1)))))
= (A 1 (A 1 (A 0 (A 1 1))))
= (A 1 (A 1 (A 0 2)))
= (A 1 (A 1 (* 2 2)))
= (A 1 (A 1 4))
= (A 1 (A 1 4))
= (A 1 (A (- 1 1) (A 1 (- 4 1))))
= (A 1 (A 0 (A 1 3)))
= (A 1 (A 0 (A (- 1 1) (A 1 (- 3 1)))))
= (A 1 (A 0 (A 0 (A 1 2))))
= (A 1 (A 0 (A 0 (A (- 1 1) (A 1 (- 2 1))))))
= (A 1 (A 0 (A 0 (A 0 (A 1 1)))))
= (A 1 (A 0 (A 0 (A 0 2))))
= (A 1 (A 0 (A 0 (* 2 2))))
= (A 1 (A 0 (A 0 4)))
= (A 1 (A 0 (* 2 4)))
= (A 1 (A 0 8))
= (A 1 (* 2 8))
= (A 1 16)
= (A (- 1 1) (A 1 (- 16 1)))
= (A 0 (A 1 15))
= (A 0 (A (- 1 1) (A 1 (- 15 1))))
= (A 0 (A 0 (A 1 14)))
= (A 0 (A 0 (A (- 1 1) (A 1 (- 14 1)))))
= (A 0 (A 0 (A 0 (A 1 13))))
= (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 13 1))))))
= (A 0 (A 0 (A 0 (A 0 (A 1 12)))))
= (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 12 1)))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 11))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 11 1))))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 10)))))))
And substituting in the result from the previous evaluation gives:
= (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 1024))))))
= (A 0 (A 0 (A 0 (A 0 (A 0 2048)))))
= (A 0 (A 0 (A 0 (A 0 (* 2 2048)))))
= (A 0 (A 0 (A 0 (A 0 4096))))
= (A 0 (A 0 (A 0 (* 2 4096))))
= (A 0 (A 0 (A 0 8192)))
= (A 0 (A 0 (* 2 8192)))
= (A 0 (A 0 16384))
= (A 0 (* 2 16384))
= (A 0 32768)
= (* 2 32768)
= 65536
And again, it may be judicious to remember that (A 2 4) evaluates to 65536...
  (A 3 3)
= (A (- 3 1) (A 3 (- 3 1)))
= (A 2 (A 3 2))
= (A 2 (A (- 3 1) (A 3 (- 2 1))))
= (A 2 (A 2 (A 3 1)))
= (A 2 (A 2 2))
= (A 2 (A (- 2 1) (A 2 (- 2 1))))
= (A 2 (A 1 (A 2 1)))
= (A 2 (A 1 2))
= (A 2 (A (- 1 1) (A 1 (- 2 1))))
= (A 2 (A 0 (A 1 1)))
= (A 2 (A 0 2))
= (A 2 (* 2 2))
= (A 2 4)
= 65536
So what about the definitions of f, g and h?

How about if we try subsititution... We need to remember that we're to provide definitions for all positive integer values of n. I.e. n > 0. Here's f:
  (f n)
= (A 0 n)
= (cond ((= n 0) 0)
        ((= 0 0) (* 2 n))
        ((= n 1) 2)
        (else (A (- 0 1)
                 (A 0 (- n 1)))))
= (cond (#f 0)
        ((= 0 0) (* 2 n))
        ((= n 1) 2)
        (else (A (- 0 1)
                 (A 0 (- n 1)))))
= (cond (#f 0)
        (#t (* 2 n))
        ((= n 1) 2)
        (else (A (- 0 1)
                 (A 0 (- n 1)))))
= (* 2 n)
So (f n) computes 2n.

Now for g. First, let's evaluate a base case, when n = 1.
  (g 1)
= (A 1 1)
= (cond ((= 1 0) 0)
        ((= 1 0) (* 2 1))
        ((= 1 1) 2)
        (else (A (- 1 1)
                 (A 1 (- 1 1))))))
= (cond (#f 0)
        ((= 1 0) (* 2 1))
        ((= 1 1) 2)
        (else (A (- 1 1)
                 (A 1 (- 1 1))))))
= (cond (#f 0)
        (#f (* 2 1))
        ((= 1 1) 2)
        (else (A (- 1 1)
                 (A 1 (- 1 1))))))
= (cond (#f 0)
        (#f (* 2 1))
        (#t 2)
        (else (A (- 1 1)
                 (A 1 (- 1 1))))))
= 2
And now for any n > 1:
  (g n)
= (A 1 n)
= (cond ((= n 0) 0)
        ((= 1 0) (* 2 n))
        ((= n 1) 2)
        (else (A (- 1 1)
                 (A 1 (- n 1))))))
= (cond (#f 0)
        ((= 1 0) (* 2 n))
        ((= n 1) 2)
        (else (A (- 1 1)
                 (A 1 (- n 1))))))
= (cond (#f 0)
        (#f (* 2 n))
        ((= n 1) 2)
        (else (A (- 1 1)
                 (A 1 (- n 1))))))
= (cond (#f 0)
        (#f (* 2 n))
        (#f 2)
        (else (A (- 1 1)
                 (A 1 (- n 1))))))
= (A (- 1 1) (A 1 (- n 1)))
= (A 0 (A 1 (- n 1)))
= (* 2 (A 1 (- n 1)))
= (* 2 (g (- n 1)))
Let's stop here a minute... When n is 1, (g n) computes 2, and when n is greater than 1, (g n) computes 2 times (g (- n 1)). In order words, (g n) computes the result of multiplying together n 2s, or to put it more succinctly, it computes 2n.

Finally, let's try h. The base case is easy enough, as it's almost identical to that of g:
  (h 1)
= (A 2 1)
= (cond ((= 1 0) 0)
        ((= 2 0) (* 2 1))
        ((= 1 1) 2)
        (else (A (- 1 1)
                 (A 1 (- 2 1))))))
= (cond (#f 0)
        ((= 2 0) (* 2 1))
        ((= 1 1) 2)
        (else (A (- 1 1)
                 (A 1 (- 2 1))))))
= (cond (#f 0)
        (#f (* 2 1))
        ((= 1 1) 2)
        (else (A (- 1 1)
                 (A 1 (- 2 1))))))
= (cond (#f 0)
        (#f (* 2 1))
        (#t 2)
        (else (A (- 1 1)
                 (A 1 (- 2 1))))))
= 2
However, for for any n > 1 is a "bit more tricky":
  (h n)
= (A 2 n)
= (cond ((= n 0) 0)
        ((= 2 0) (* 2 n))
        ((= n 1) 2)
        (else (A (- n 1)
                 (A n (- 2 1)))))
= (cond (#f 0)
        ((= 2 0) (* 2 n))
        ((= n 1) 2)
        (else (A (- n 1)
                 (A n (- 2 1)))))
= (cond (#f 0)
        (#f (* 2 n))
        ((= n 1) 2)
        (else (A (- n 1)
                 (A n (- 2 1)))))
= (cond (#f 0)
        (#f (* 2 n))
        (#f 2)
        (else (A (- n 1)
                 (A n (- 2 1)))))
= (A (- n 1) (A n (- 2 1)))
= (A (- n 1) (A n 1))
... and so on. Let's not do that.

Instead, let's try some substitutions for small values of n. We know already that (h 1) is 2, so let's try with the subsequent values of n... And you'll forgive me, I hope, if skip the step-by-step evaluations of cond operators...
  (h 2)
= (A 2 2)
= (A (- 2 1) (A 2 (- 2 1)))
= (A 1 (A 2 1))
= (A 1 2)
= (g 2)
We know that (g n) computes 2n, so (g 2) (and therefore (h 2)) computes 22.
  (h 3)
= (A 2 3)
= (A (- 2 1) (A 2 (- 3 1)))
= (A 1 (A 2 2))
= (A 1 4))
= (g 4)
= 24
= 16
Note that we substitutute 4 for (A 2 2). This comes from the evaluation of (h 2) above. We'll apply similar substitutions below.
  (h 4)
= (A 2 4)
= (A (- 2 1) (A 2 (- 4 1)))
= (A 1 (A 2 3))
= (A 1 (g 4))
= (A 1 16)
= (g 16)
= 216
= 65536

  (h 5)
= (A 2 5)
= (A (- 2 1) (A 2 (- 5 1)))
= (A 1 (A 2 4))
= (A 1 65536)
= (g 65536)
= 265536
= a very big number
Okay, I think that's enough.

(h n) calculates 2(h (- n 1)), with (h 1) evaluating to 2. So (h 2) evaluates to 22, (h 3) evaluates to 222, (h 4) evaluates to 2222 and so on. This type of iterative exponentation is known as tetration, which thankfully has a nice concise way of being expressed: (h n) computes n2.
Posted by at
Labels: ,

4 comments:

  1. mattDecember 28, 2013 at 8:55 PM

    I worked out the solution for (h n) before reading your post, but I had no idea what that pattern of 2^2^2^2... was called or how it could be expressed. Very useful, thanks!

    ReplyDelete
    Replies
    1. joaojgabrielMay 9, 2022 at 1:38 AM

      So did I, and I'm very thankful there is such a thing. Spent a lot of time trying to work it out in my head, though xD like "how the heck could you bend this pattern to one that I already know a way to express in notation?"

      Delete
  2. shadowdrakkenApril 25, 2016 at 9:01 AM

    Awesome

    ReplyDelete
  3. UnknownMarch 18, 2017 at 5:48 AM

    Very helpful—

    ReplyDelete

Subscribe to: Post Comments (Atom)