CS 22

Clab 38: One Wierd Function
Why Nondeterministic Computing Would Be Nice

Ackermann's Function: One Wierd Function

Now I want you to take a look at a very interesting function. Mathematicians like the successor function a lot. In some sense, a great deal of mathematics can be built from recursion and the successor function. Here we will use successor and predecessor to build an interesting function first discovered last century by Ackermann. Put this in a drscheme definition window.

(define pred (lambda (x) (- x 1))) (define succ (lambda (x) (+ x 1))) (define (A z x y) (cond ((= z 0) (if (= x 0) y (succ (A 0 (pred x) y)))) ((= x 0) (if (= z 1) 0 1)) (else (A (pred z) (A z (pred x) y) y)))) (require-library "trace.ss") This is only for natural numbers, so x, y, z should always be non-negative. Now try a couple of evaluations for small values of z (<= 2) and small x and y (<= 10).

  1. Suppose you define a(x, y) = (A 0 x y). What is a(x, y) ? You know it under another name.
  2. Suppose you define m(x, y) = (A 1 x y). What is m(x, y) ? You know it under another name.
  3. Suppose you define e(x, y) = (A 2 x y). What is e(x, y) ? You know it under another name.
  4. You probably don't know another name for (A 3 x y). But can you describe it in terms of x and y? THINK.
Now put trace on pred and succ. With trace on, try evaluations of (A 1 4 5) and (A 2 3 4) in ordinary drscheme. Think about what you get. Think about the process generated by A.

Then contrast the results you get when you evaluate (A 2 7 2) in the driver-loop of mcevaltime a couple of times and in anevaltime a couple of times. Analyzing first is good!

If you define a Ack(x) to be (A x x x) then Ack is an increasing function that grows extremely rapidly. In fact, Ack(4) is bigger than the number of electrons in the universe (also bigger than the number of micro-seconds since the big-bang). If we let AckInv be the inverse function of Ack, then AckInv is an increasing function but a very sloooooowly increasing function. For any big number B, you could have thought of before you saw the definition of A, AckInv(B) < 6. Now here is an interesting fact (take CS41 and CS46 for more details). There are some interesting, naturally-occuring, useful problems for which we know there cannot be O(n) algorithms but for which we have O(n x AckInv(n)) algorithms. What this means is that the natural world is weird. :-)

Why Nondeterministic Computing Would Be Nice

We will soon look at a whole new way to do things. It's called non-deterministic computing. It may or may not be magic. But we can make a modified evaluator do it. Unfortunately, on ordinary computers, raw non-deterministic computing is very inefficient. But, if physicists can build modest size quantum computers, this will be an efficient way to program.

Before we really dig into this though I want you to spend the rest of this clab on some exercises. It is my hope that you will agree that these are not trivial in any of the ordinary imperative, functional, or object-oriented styles of programming. On Friday, we will see that they are easy in a non-deterministic, declarative style of programming.

  1. In your favorite language, write a function that will take a list (or array) as an argument and return all the permutations of that list (or array) either one at a time or in another collection.
  2. In your favorite language, write a program to solve: Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?
  3. The eight queens problem ex2.42 on page 124-126. (you can get this on the web by going to: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2.4 and backing up several screeen-fulls. (Here the hardest conceptual work is done for you, but make sure you thoroughly understand it.)

Next clab, I'll show you how to do these nondeterministically. Here is a sample run of my permutation function.

;;; Amb-Eval input: (nond-perm '(a b c)) ;;; Starting a new problem ;;; Amb-Eval value: (a b c) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (a c b) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (b a c) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (b c a) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (c a b) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (c b a) ;;; Amb-Eval input: try-again ;;; There are no more values of (nond-perm '(a b c))