ELEMENTARY - Definition

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 y ≥ x. 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:

    “Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
    —The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)

    “... 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 definition of good prose is proper words in their proper places; of good verse, the most proper words in their proper places. The propriety is in either case relative. The words in prose ought to express the intended meaning, and no more; if they attract attention to themselves, it is, in general, a fault.”
    —Samuel Taylor Coleridge (1772–1834)