Primitive recursive function

In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop is fixed before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions.

The importance of primitive recursive functions lies in the fact that most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive. For example, addition and division, the factorial and exponential function, and the function which returns the nth prime are all primitive recursive. In fact, for showing that a computable function is primitive recursive, it suffices to show that its time complexity is bounded above by a primitive recursive function of the input size. It is hence not particularly easy to devise a computable function that is not primitive recursive; some examples are shown in section § Limitations below.

The set of primitive recursive functions is known as PR in computational complexity theory.

Cnk: For each natural number Cnk(x1,…,xk) =def n, is primitive recursive.

Successor function: The 1-ary successor function S, which returns the successor of its argument (see Peano postulates), that is, i,k such that

4. Composition operator g1(x1,…,xk),…,gm(x1,…,xk): h∘g1 is obtained.
5. Primitive recursion operator (k+2)-ary function f acts as a for-loop from x1,…,xk, are a set of initial conditions for the for-loop which may be used by it during calculations but which are immutable by it. The functions f represent the body of the loop, which performs calculations. The function h is fed the "current" value of the for-loop's index. The second parameter of h to perform calculations but they will not themselves be altered by f(x1,…,xm)=(f1(x1,…,xm),…,fn(x1,…,xm))

   where each component C01 is a 1-ary function which returns C11 is a 1-ary function which returns C30 is a 0-ary function, i.e. a constant: P11(x)=x.

6. P12(x,y)=x and (S∘S)(x)=x+2.
7. S∘C01 and Cnk can be expressed as a composition of appropriately many C0k equals Cnk only for Add, to compute the sum of its arguments, can be obtained using the primitive recursion operator ρ(g,h), the first equation suggests to choose h=S∘P23 to obtain Add⁡(1,7)=ρ(P11,S∘P23)(S(0),7) by Def. Add⁡,S=(S∘P23)(0,Add⁡(0,7),7) by case ρ(g,h)(S(...),...)=S(Add⁡(0,7)) by Def. ∘,P23=S(ρ(P11,S∘P23)(0,7)) by Def. Add=S(P11(7)) by case ρ(g,h)(0,...)=S(7) by Def. P11=8 by Def. S.

   Doubling

   edit

   Given (Add⁡∘(P11,P11))(x)=Add⁡(x,x)=x+x.

   Multiplication

   edit

   In a similar way as addition, multiplication can be defined by Mul⁡(S(x),y)=ρ(C01,Add⁡∘(P23,P33))(S(x),y) by Def. Mul=(Add⁡∘(P23,P33))(x,Mul⁡(x,y),y) by case ρ(g,h)(S(...),...)=Add⁡(Mul⁡(x,y),y) by Def. ∘,P23,P33=Mul⁡(x,y)+y by property of Add⁡.

   Predecessor

   edit

   The predecessor function acts as the "opposite" of the successor function and is recursively defined by the rules Pred⁡=ρ(C00,P12). As a computation example,

   RSub⁡=ρ(P11,Pred⁡∘P23). To get rid of the reversed argument order, then define t for true, and t with the number 0. Once this identification has been made, the characteristic function of a set 0, can be viewed as a predicate that tells whether a number is in the set Predicate "Is zero"edit