Mark your calendar
CS 46 Comprehensive Final Exam is scheduled for Friday, 8 May 9am-12n in Sci 264.


Due: Wednesday, Mar. 18

1. Think for a while about what we should mean when we say a problem (or function) is computable either by a human with a pencil and paper or a computer. Remember that before 1940 a 'computer' was a person who did computations. (Check it out in an old dictionary.) It has only been since about 1950 that 'computer' has referred to a machine.

   There is a lot to think about here, so feel free to think about this stuff wherever you are. There is nothing better than a good theory conversation on the beach.

2. Consider the following function:
   f(0, 0, y) = y
   f(0, x+1, y) = f(0, x, y) + 1 for x>=0
   f(1, 0, y) = 0
   f(z+2, 0, y) = 1 for z>=0
   f(z+1, x+1, y) = f(z, f(z+1, x, y), y) for x>=0 and z>=0
   end of definition of function.

   Think about this function. Is it computable? You might write a program to compute it. Try it for small values of z,x,y. Using the Unix utility nice, try evaluating f(5, 5, 5). Do NOT try this without using nice unless you are doing it on your own private machine. And if you do that, save anything valuable before you start the evaluation.

   a)Suppose you define a(x, y) = f(0, x, y). What is a(x, y) ? You know it under another name.

   b)Suppose you define m(x, y) = f(1, x, y). What is m(x, y) ? You know it under another name.

   c) Suppose you define e(x, y) = f(2, x, y). What is e(x, y) ? You know it under another name.

   d)You probably don't know another name for f(3, x, y). But can you describe it in terms of x and y? THINK.

3. Write solutions to a,b,c,d above, and 3 of: 4.5.1b, 4.5.2, 4.5.3, 4.6.2b, 4.6.2c.