Non User
Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z	Business Non User Industries Finance Tax

Home > Primitive recursive function

Many of the functions normally studied in number theory, and approximations to real-valued functions, are primitive recursive. such as addition, division, factorial, finding the nth prime, and so on. In fact, it's quite difficult to devise a function that is not primitive recursive. Thus, by studying them, we can discover properties that have wide-reaching consequences.

1 Definition

Primitive recursive functions take natural numbers or tuples of natural numbers as arguments and produce a natural number. A function which takes n arguments is called n- ary. The basic primitive recursive functions are given by these axioms:

1. The constant function 0 is primitive recursive.
2. The successor function S, which takes one argument and returns the succeeding number as given by the Peano postulates, is primitive recursive.
3. The projection functions P_iⁿ, which take n arguments and return their ith argument, are primitive recursive.

More complex primitive recursive functions can be obtained by applying the operatorThis article is about operators in mathematics, for other kinds of operators see operator (disambiguation). In mathematics, an operator is some kind of function; if it comes with a specified type of operand as function domain, it is no more than another ws given by these axioms:

1. Composition: Given f, a k-ary primitive recursive function, and k l-ary primitive recursive functions g₀,...,g_k-1, the composition of f with g₀,...,g_k-1, i.e. the function h(x₀,...,x_l-1) = f(g₀(x₀,...,x_l-1),...,g_k-1(x₀,...,x_l-1)), 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 defined as the primitive recursion of f and g, i.e. the function h where h(0,x₀,...,x_k-1) = f(x₀,...,x_k-1) and h(S(n),x₀,...,x_k-1) = g(h(n,x₀,...,x_k-1),n,x₀,...,x_k-1), is primitive recursive.

(Note that the projection functions allow us to get around the apparent rigidity in terms of the arity of the functions above, as via composition we can pass any subset of the arguments.)

A function is primitive recursive if it is one of the basic functions above, or can be obtained from one of the basic functions by applying the operations a finite number of times.

2 Examples

2.1 Addition

Intuitively we would like to define addition recursively as:

add(0,x)=x

add(n+1,x)=add(n,x)+1

In order to fit this into a strict primitive recursive definition, we define:

add(0,x)=P₁¹(x)

add(S(n),x)=S(P₁³(add(n,x),n,x))

(Note: here P₁³ is a function, which takes 3 arguments and returns the first one.)

Note that P₁¹ is simply the identity functionAn identity function ''f is a function which doesn't have any effect: it always returns the same value that was used as its argument. Formally, if M is a set, we define the identity function id on M to be that function with domain and codomain M which sat; its inclusion is required by the definition of the primitive recursion operator above; it plays the role of f. The composition of S and P₁³, which is primitive recursive, plays the role of g.

Politics	Business	Finance

Topics: Primitive Recursive Function Functions Computable Arguments...

---

Primitive notionIn mathematics, a primitive notion is something that is not defined in terms of previously defined terms. That is, it is something that is taken to be true as an axiom rather than something that can be proved from a set of further axioms. For example in n Primitive recursive functionIn computability theory, primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. They are defined using recursion and composition as central operations and are a st Primitive LyricsPrimitive Lyrics is a hip hop crew from Switzerland, formed out of the members of Graffiti Crew UC from Zurich. The group was one of the first Swiss dialect hip hop crews. Their first album was 1992's Halbi Nuni Chloricht''. The follow-up was 1996's FLAG' PrimitiveThe word primitive can refer to: primitive art and Primitivism (art) primitive (biology) primitive (computer science) primitive (linguistics) primitive (mathematics) primitive (ontology) Primitive (song). Primitive root modulo nPrimitive roots modulo n are a concept from modular arithmetic, in number theory. If n ge;1 is an integer, the numbers coprime to n taken modulo n form a group with multiplication as operation; it is written as Z ''n Z × or Z . This group is cyclic if and Primitive (song)Primitive a song written and performed by 1980s icon and singer Cyndi Lauper, appeared on her 1989 album A Night to Remember which bombed commercially. However, this song became a Dutch hit single and reached #1 in the Netherlands music charts. Primitive equations Primitive semiperfect number Primitive Baptist Primitive element Primitive type Primitive (album) Primitive Advent Christian Church Primitive root Primitive element (field theory)