examples of primitive recursive functions
Starting from the simplest primitive recursive functions, we can build more complicated primitive recursive functions by functional
composition and primitive recursion. In this entry, we have listed some basic examples using functional composition alone. In this entry, we list more basic examples, allowing the use of primitive recursion:
- 1.
: , and
- 2.
: , and .
- 3.
, which is just ; more generally, , which is primitive recursive by induction
on
- 4.
: , and
- 5.
: , and
- 6.
: , and
- 7.
built using and : , and ;
- 8.
more generally, may be defined: .
- 9.
: , and .
- 10.
- 11.
built using and : , and .
- 12.
more generally,
is primitive recursive, for it is .
- 13.
even more generally,
where , is primitive recursive, for it is .
- 14.
which is just .
- 15.
where is the remainder of . Suppose . Then . In addition
,
Then , and
where . The reason for including is to account for the case when .
- 16.
To see that is primitive recursive, we use equation
obtained from the division algorithm for integers. Then
Simplify and we get
Thus, by the previous example, we get
Therefore, , and
where takes the case into account.
Remarks.
- •
All of the functions above are in fact examples of elementary recursive functions.
- •
Example 3(m) above is a special case of a more general phenomenon. Recall that a subset is called primitive recursive if its characteristic function
is primitive recursive. If we take , then . Furthermore, a predicate
over is primitive recursive if the corresponding set is primitive recursive.
- •
The technique of bounded maximization may be used to prove the primitive recursiveness of the quotient
and the reminder functions in examples 3(o) and 3(p). See this entry (http://planetmath.org/BoundedMaximization) for more detail.