Models of Computation - Mathematics 352 - Fall 2009

For HW #8

1. Define f(x,y) as x-y when x is greater than or equal to y, and undefined otherwise.
   1. Prove f is computable.
   2. Is f primitive recursive? Explain.
2. Define f(n) as follows:
   f(0) = 1;
   f(n) = f(0) + f(1) +  ... + f(n-1)   if n > 0.
   1. Find f(100).  (Use a spreadsheet or Mathematica or any other software you'd like, or write a program in URM language or C or Java or any other language you'd like!)
   2. Prove that f is computable.
   3. Is f primitive recursive? Explain.
3. 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.
   1. Prove that f is computable. (Hint: look at the Fibonacci exercise in the book.)
   2. Is f primitive recursive? Explain.
4. Define f(n) as follows:
   f(0) = 1;
   f(n) = (n)f(0) + (n+1)f(1) + (n+2)f(2) + ... + (n+n-1)f(n-1)  if n > 0.
   1. Find f(30).  (Use a spreadsheet or Mathematica or any other software you'd like, or write a program in URM language or C or Java or any other language you'd like!)
   2. Prove that f is computable. (Hint: Let g(n) = 2^f(0) 3^f(1) ... p_(n+1)^f(n), where p_(n+1) denotes the (n+1)th prime number. First show g is computable. Then show f is computable.)
   3. Is f primitive recursive? Explain.