COSC 4111 AF - Exercises

  Exercise 2,3 in Notes,  p. 56

  Exercise 4 in Notes, p. 57

  Prove if g and h are unary computable functions, so is f(x)=g(h(x))

  (*)  Prove formally that factorial is primitive recursive.  Hand in Tuesday January 19. 

  Can you also show factorial is primitive recursive if we define 
factorial(0) to be 1 instead of 0?

 (*) Prove the fibonacci function fib(0) = fib(1) = 1; fib (y+2) = fib(y+1) + fib(y) is primitive recursive. (Hand in Thursday January 21.)

  Ackermann's Function: (a) What is the value of A_4 on 0, 1, 2, 3, 4?
(b) Prove each function A_n is primitive recursive.

  Exercise 6 on page 58.

 Exercise 8 - p. 64

 Exercise 10 on p.65

 (*) Exercise 12 on p.69.  (Please hand in on February 4)

 (*?) Exercise 14 on p.70  (or hand this one in on Feb 4 for extra credit.)