elementary recursive function


Informally, elementary recursive functions are functionsMathworldPlanetmath that can be obtained from functions encountered in elementary schools: additionPlanetmathPlanetmath, multiplication, subtractionPlanetmathPlanetmath, and division, using basic operationsMathworldPlanetmath such as substitutions and finite summation and productMathworldPlanetmath. Before stating the formal definition, the following notations are used:

={Fkk}, where for each kFk={ff:k}.

Definition. The set of elementary recursive functions, or elementary functions for short, is the smallest subset of where:

  1. 1.

    (addition) addF2, given by add(m,n):=m+n;

  2. 2.

    (multiplication) multF2, given by mult(m,n):=mn;

  3. 3.

    (differencePlanetmathPlanetmath) diffF2, given by diff(m,n):=|m-n|;

  4. 4.

    (quotient) quoF2, given by quo(m,n):=[m/n], which is the largest non-negative integer z such that nzm (by convention, quo(0,0):=1);

  5. 5.

    (projection) pmkFk, where mk, given by pmk(n1,,nk):=nm;

  6. 6.

    is closed under composition: If {g1,,gm}Fk and hFm, then fFk, where

    f(n1,,nk)=h(g1(n1,,nk),,gm(n1,,nk));
  7. 7.

    is closed under bounded sum: if fFk, then fsFk, where

    fs(𝒙,y):=i=0yf(𝒙,i);
  8. 8.

    is closed under bounded product: if fFk, then fpFk, where

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

Examples.

  • The initial functions in the definition of primitive recursive functionsMathworldPlanetmath are elementary:

    1. (a)

      The zero function z(x) is diff(x,x).

    2. (b)

      The constant functionMathworldPlanetmath const1(x):=1 is quo(x,x).

    3. (c)

      The successor function s(x) can be obtained by substituting (by composition) the constant function const1 and the projection function p11, into the addition function add(p11(x),const1(x)).

  • Multiplication mult in 2 above may be removed from the definition, since

    mult(x,y)=diff(f(x,y),p12(x,y)),where f(x,y):=i=0yp12(x,i)
  • Many other basic functions, such as the restricted subtraction, exponential functionDlmfDlmfMathworld, the i-th prime function, are all elementary. One may replace the difference function in 3 above by the restricted subtraction without changing .

Remarks

  • 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 f(x,0)=m, and f(x,n+1)=exp(m,f(x,n)), where m>1, 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.

  • By taking the closure of with respect to unbounded minimization, one obtains , the set of all recursive functions (partial or total). In fact, by replacing bounded sum and bounded product with unbounded minimization, and the difference function with restricted subtraction, one obtains .

Title elementary recursive function
Canonical name ElementaryRecursiveFunction
Date of creation 2013-03-22 19:06:48
Last modified on 2013-03-22 19:06:48
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 9
Author CWoo (3771)
Entry type Definition
Classification msc 03D20
Synonym elementary
Related topic BoundedRecursion
Defines elementary recursive