bounded minimization


One useful way of generating more primitive recursive functionsMathworldPlanetmath from existing ones is through what is known as bounded summation and bounded product. Given a primitive recursive function f:m+1, define two functions fs,fp:m+1 as follows: for 𝒙m and y:

fs(𝒙,y):=i=0yf(𝒙,i)
fp(𝒙,y):=i=0yf(𝒙,i)

These are easily seen to be primitive recursive, because they are defined by primitive recursion. For example,

fs(𝒙,0)=f(𝒙,0),andfs(𝒙,n+1)=g(𝒙,n,fs(𝒙,n)),

where g(𝒙,n,y)=add(f(𝒙,n),y), which is primitive recursive by functionalPlanetmathPlanetmathPlanetmathPlanetmath compositionMathworldPlanetmath.

Definition. We call fs and fp functions obtained from f 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 f:m+1 be a function. For each y, set

Af(𝒙,y):={zzy and f(𝒙,z)=0}.

Define

fbmin(𝒙,y):={minAf(𝒙,y)if Af(𝒙,y),s(y)otherwise.

fbmin is called the function obtained from f by bounded minimization, and is usually denoted

μzy(f(𝒙,z)=0).
Proposition 1.

If f:Nm+1N is primitive recursive, so is fbmin.

Proof.

Define g:=sgnf. Then

g(𝒙,y):={0if f(𝒙,y)=0,1otherwise.

As f is primitive recursive, so is g, since the sign function sgn is primitive recursive (see this entry (http://planetmath.org/ExamplesOfPrimitiveRecursiveFunctions)).

Next, the function gp obtained from g by bounded product has the following properties:

  • if gp(𝒙,y)=1, then gp(𝒙,z)=1 for all z<y,

  • if gp(𝒙,y)=0, then gp(𝒙,z)=0 for all zy.

Finally, the function (gp)s obtained from gp by bounded sum has the property that, when applied to (𝒙,y), counts the number of zy such that gp(𝒙,z)=1. Based on the property of gp, this count is then exactly the least zy such that gp(𝒙,z)=1. This means that (gp)s=fbmin for all (𝒙,y)m+1. Since gp is primitive recursive, so is (gp)s, or that fbmin is primitive recursive. ∎

In fact, if f is a (total) recursive function, so is fbmin, 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 y out, then we arrive at the notion of unbounded minimization, or just minimization. The propositionPlanetmathPlanetmathPlanetmath 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