Models of Computation - Mathematics 450 - Spring 2005

For HW #8

1. Define f(x,y) as x-y when x is greater than or equal to y, and undefined otherwise. Prove f is computable.
2. Define f(n) as follows:
   f(0) = f(1) = f(2) = 1;
   f(n) = f(n-1) + f(n-2) + f(n-3), for n > 2.
   Prove that f is computable. (Hint: look at the Fibonacci exercise in the book.)
3. Let f(n) = the sum of the distinct prime factors of n. For example, f(3) = 3, f(6) = 2+3 = 5, f(24) = 2+3 = 5, f(25) = 5. Define f(0) however is convenient for you! Prove f is computable.