In this entry, the following notations are used:
, where for each , and .
is defined by primitive recursion via and :
is bounded from above by :
Clearly, a function that is defined by bounded recursion is defined by primitive recursion. Conversely, a function is defined by primitive recursion, it is also defined by bounded recursion, since it is bounded by itself. However, the two concepts are not exactly the same. To make this precise, we first define what it means for a set of number-theoretic functions be closed under bounded recursion:
Definition. A set is said to be closed under bounded recursion if, for any defined by bounded recursion via , then .
It is clear that is closed under both primitive recursion and bounded recursion, and so are , the set of all primitive recursive functions, as well as , the set of all total recursive functions. However,
The set of all elementary recursive functions is closed under bounded recursion, but not primitive recursion.
If is defined by course-of-values recursion via an elementary recursive function , and is bounded from above by an elementary recursive function , then is elementary recursive.
|Date of creation||2013-03-22 19:07:01|
|Last modified on||2013-03-22 19:07:01|
|Last modified by||CWoo (3771)|
|Synonym||bounded primitive recursion|