CS 5315 Homework #2

Date Assigned: Thursday, January 20, 2005

Due Date: Tuesday, January 25, 2005

1. In the class, we proved that if P(n) is a primitive recursive predicate, and f(n) and g(n) are primitive recursive functions, then the function "if P(n) then f(n) else g(n)" is also primitive recursive. Use the ideas from this proof to prove that if P1(n) and P2(n) are primitive recursive predicates, and f(n), g(n), and h(n) are primitive recursive functions, then the function "if P1(n) then f(n) else if P2(n) then g(n) else h(n)" is also primitive recursive.

2. Show that the function pow(a,n)=a^n (a to the power n) is a primitive recursive function.