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.