Primitive recursive function

A function from natural numbers to natural numbers which can be obtained from the initial functions

by a finite number of the operations of composition and primitive recursion.

Since the initial functions are computable and the operators of superposition and primitive recursion preserve computability, the set of all primitive recursive functions is a subclass of the class of all computable functions (cf. Computable function). Every primitive recursive function is specified by a description of its construction from the initial functions (a primitive recursive description); hence the class of primitive recursive functions is countable. Practically all arithmetic functions used in mathematics for some concrete reason are primitive recursive functions; e.g. , , , , (the remainder from division of by ), (the prime number with index ), etc.

A relation on natural numbers is called a primitive recursive relation if the function , equal to 1 if is true and 0 if is false, is primitive recursive. One says that the relation has been obtained from a relation by means of a bounded quantifier if

or

The class of primitive recursive relations is closed under the application of logical connectives (including negation) and bounded quantifiers.

Suppose that are -place primitive recursive functions, and let be primitive recursive relations such that for any set of argument values at most one of them is true. Then the function

(*)

is primitive recursive.

One says that the function has been obtained from an everywhere-defined function by means of the bounded minimization operator if is equal to the minimal such that and , and is equal to otherwise. The class of primitive recursive functions is closed under bounded minimization operators.

A function is called universal for the class of -place primitive recursive functions if for each such function there is a natural number such that

There exists a universal function for every , but it need not be primitive recursive.

Every recursively enumerable set is the range of values of a primitive recursive function; every recursively enumerable relation can be represented as , where is a primitive recursive relation. Every primitive recursive function can be represented in formal arithmetic (cf. Arithmetic, formal); i.e. for each primitive recursive function there is an arithmetical formula such that for all natural numbers , the formula is derivable in formal arithmetic if , while is derivable if . (Here are arithmetical terms reflecting the natural numbers in formal arithmetic.) This fact takes a central position in the proof of the incompleteness of formal arithmetic (cf. [4]).

References

[1]	V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian)
[2]	A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)
[3]	H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165
[4]	E. Mendelson, "Introduction to mathematical logic" , v. Nostrand (1964)

Comments

The fact that the function (*) is primitive recursive under the given assumptions is often rephrased as: the class of primitive recursive functions is closed under "definition by cases" .

References

[a1]	C. Calude, "Theories of computational complexity" , North-Holland (1988)