## 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.

Answer:
We can rewrite the desired function as "if P1(n) then f(n) else G(n)",
where G(n) denotes the function "if P2(n) then g(n) else h(n)".
Since P2(n), g(n), and h(n) are primitive recursive, the function G(n)
is also primitive recursive.
Since P1(n), f(n), and G(n) are primitive recursive, the desired
function "if P1(n) then f(n) else G(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.

Answer:
By definition, n^m means n * n * ... * n (m times). Thus:
pow(n,0) = 1
pow(n,m+1) = n * pow(n,m)
In general, for a primitive recursive function of two variables,
f(n,0) = g(n)
f(n,m+1) = h(n,m,f(n,m))
In this case,
f(n,0) = 1
f(n,m+1) = n * f(n,m)
Thus, here g = 1 = sigma(0) and h(n,m,f) = n*f.