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:
- Constant function: The 0-ary constant function 0 is primitive recursive.
- 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.
- 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:
- 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.
- 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:
“The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
—William James (18421910)
“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 (17721834)
“Mothers often are too easily intimidated by their childrens negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)