bounded minimization
One useful way of generating more primitive recursive functions from existing ones is through what is known as bounded summation and bounded product. Given a primitive recursive function , define two functions as follows: for and :
These are easily seen to be primitive recursive, because they are defined by primitive recursion. For example,
where , which is primitive recursive by functional composition.
Definition. We call and functions obtained from by bounded sum and bounded product respectively.
Using bounded summation and bounded product, another useful class of primitive recursive functions can be generated:
Definition. Let be a function. For each , set
Define
is called the function obtained from by bounded minimization, and is usually denoted
Proposition 1.
If is primitive recursive, so is .
Proof.
Define . Then
As is primitive recursive, so is , since the sign function is primitive recursive (see this entry (http://planetmath.org/ExamplesOfPrimitiveRecursiveFunctions)).
Next, the function obtained from by bounded product has the following properties:
-
•
if , then for all ,
-
•
if , then for all .
Finally, the function obtained from by bounded sum has the property that, when applied to , counts the number of such that . Based on the property of , this count is then exactly the least such that . This means that for all . Since is primitive recursive, so is , or that is primitive recursive. ∎
In fact, if is a (total) recursive function, so is , because all of the derived functions in the proof above preserve primitive recursiveness as well as totalness.
Remarks.
-
•
In the definition of bounded minimization, if we take the out, then we arrive at the notion of unbounded minimization, or just minimization. The proposition above shows that the set of primitive recursive functions is closed under bounded minimization. However, is not closed under minimization. The closure of under minimization is the set of recursive functions (total or not).
-
•
It is not hard to show that , the set of all elementary recursive functions, is closed under bounded minimization.
Title | bounded minimization |
Canonical name | BoundedMinimization |
Date of creation | 2013-03-22 19:05:18 |
Last modified on | 2013-03-22 19:05:18 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 11 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 03D20 |
Synonym | bounded sum |
Related topic | UnboundedMinimization |
Related topic | RecursiveFunction |
Related topic | BoundedMaximization |
Defines | bounded summation |
Defines | bounded product |