ELEMENTARY - Definition


The definitions of elementary recursive functions are the same as for primitive recursive functions, except that primitive recursion is replaced by bounded summation and bounded product. All functions work over the natural numbers. The basic functions, all of them elementary recursive, are:

  1. Zero function. Returns zero: f(x) = 0.
  2. Successor function: f(x) = x + 1. Often this is denoted by S, as in S(x). Via repeated application of a successor function, one can achieve addition.
  3. Projection functions: these are used for ignoring arguments. For example, f(a, b) = a is a projection function.
  4. Subtraction function: f(x, y) = x - y if y < x, or 0 if yx. This function is used to define conditionals and iteration.

From these basic functions, we can build other elementary recursive functions.

  1. Composition: applying values from some elementary recursive function as an argument to another elementary recursive function. In f(x1, ..., xn) = h(g1(x1, ..., xn), ..., gm(x1, ..., xn)) is elementary recursive if h is elementary recursive and each gi is elementary recursive.
  2. Bounded summation: is elementary recursive if g is elementary recursive.
  3. Bounded product: is elementary recursive if g is elementary recursive.

Read more about this topic:  ELEMENTARY

Famous quotes containing the word definition:

    According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.
    Ana Castillo (b. 1953)

    ... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.
    George Eliot [Mary Ann (or Marian)

    The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.
    Ralph Waldo Emerson (1803–1882)