Primitive Recursive Function - Definition

Definition

The primitive recursive functions are among the number-theoretic functions, which are functions from the natural numbers (nonnegative integers) {0, 1, 2, ...} to the natural numbers. These functions take n arguments for some natural number n and are called n-ary.

The basic primitive recursive functions are given by these axioms:

  1. Constant function: The 0-ary constant function 0 is primitive recursive.
  2. Successor function: The 1-ary successor function S, which returns the successor of its argument (see Peano postulates), is primitive recursive. That is, S(k) = k + 1.
  3. Projection function: For every n≥1 and each i with 1≤i≤n, the n-ary projection function Pin, which returns its i-th argument, is primitive recursive.

More complex primitive recursive functions can be obtained by applying the operations given by these axioms:

  1. Composition: Given f, a k-ary primitive recursive function, and k m-ary primitive recursive functions g1,...,gk, the composition of f with g1,...,gk, i.e. the m-ary function is primitive recursive.
  2. Primitive recursion: Given f, a k-ary primitive recursive function, and g, a (k+2)-ary primitive recursive function, the (k+1)-ary function h is defined as the primitive recursion of f and g, i.e. the function h is primitive recursive when
    and

The primitive recursive functions are the basic functions and those obtained from the basic functions by applying these operations a finite number of times.

Read more about this topic:  Primitive Recursive Function

Famous quotes containing the word definition:

    “... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
    —Adrienne Rich (b. 1929)

    “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)

    “No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
    —Florence Nightingale (1820–1910)