Intuitively, a recursive function is a positive integer valued function of one or more positive integer arguments which may be computed by a definite algorithm. Recursive functions may be defined more rigorously as the smallest class of partial functions from z4z, satisfying the following six criteria: 1. The constant function c:z,z, defined by c(z)=1 for all xz, is a recursive function. 2. The addition function +zz2z4 and the multiplication function x:z,z, are recursive function. 3. The projection functions I:zz,, with 1mn defined as I(x1,,x)=x are recursive functions. 4. (Closure under composition) If fi=z4z2, is a recursive function and s1:zz4 with i=1,,n are recursive functions, then A:zzz, defined by h(x1,,z)=f(g1(x1,,xm),,gn(z1,,x)) is a recursive function. 5. (Closure under primitive recursion) If f:ztz, and g:z++2z, are recursive function, then h:z2+1z2, defined by the recursion with the initial condition is a recursive function. 6. (Closure under minimization) If f:ztz, is a recursive function then g:zqz, is a recursive function, where g(x1,,zn) is defined to be yy, if there exists a yz, such that i. f(0,x1,,xn),f(1,x1,,xn),,f(y,x1,,xn) are all defined, ii. f(x,x1,,xn)=0 when 1x