elementary recursive function
Informally, elementary recursive functions are functions that can be obtained from functions encountered in elementary schools: addition, multiplication, subtraction, and division, using basic operations such as substitutions and finite summation and product. Before stating the formal definition, the following notations are used:
, where for each .
Definition. The set of elementary recursive functions, or elementary functions for short, is the smallest subset of where:
(addition) , given by ;
(multiplication) , given by ;
(difference) , given by ;
(quotient) , given by , which is the largest non-negative integer such that (by convention, );
(projection) , where , given by ;
is closed under composition: If and , then , where
is closed under bounded sum: if , then , where
is closed under bounded product: if , then , where
The initial functions in the definition of primitive recursive functions are elementary:
Multiplication in 2 above may be removed from the definition, since
Many other basic functions, such as the restricted subtraction, exponential function, the -th prime function, are all elementary. One may replace the difference function in 3 above by the restricted subtraction without changing .
Consider the set of primitive recursive functions. The functions in the first five groups above are all in . In addition, is closed under the operations in 6, 7, and 8 above, we see that , since , as defined, is the smallest such set.
Furthermore, . For example, the super-exponential function, given by , and , where , can be shown to be non-elementary.
In addition, it can be shown that is the set of primitive recursive functions that can be obtained from the zero function, the successor function, and the projection functions via composition, and no more than three applications of primitive recursion.
|Title||elementary recursive function|
|Date of creation||2013-03-22 19:06:48|
|Last modified on||2013-03-22 19:06:48|
|Last modified by||CWoo (3771)|