Primitive recursive function

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

$$ s ( x) = x + 1,\ \ o ( x) = 0,\ \ I _ {m} ^ {n} ( x _ {1} \dots x _ {n} ) = x _ {m} $$

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. $ x + y $, $ x \cdot y $, $ x ^ {y} $, $ \mathop{\rm sign} ( x) $, $ [ x/y] $( the remainder from division of $ x $ by $ y $), $ \pi ( x) $( the prime number with index $ x $), etc.

A relation $ P ( x _ {1} \dots x _ {n} ) $ on natural numbers is called a primitive recursive relation if the function $ g ( x _ {1} \dots x _ {n} ) $, equal to 1 if $ P ( x _ {1} \dots x _ {n} ) $ is true and 0 if $ P ( x _ {1} \dots x _ {n} ) $ is false, is primitive recursive. One says that the relation $ P ( x _ {1} \dots x _ {n} , z) $ has been obtained from a relation $ Q ( x _ {1} \dots x _ {n} , y, z) $ by means of a bounded quantifier if

$$ P ( x _ {1} \dots x _ {n} , z) \iff \ \forall y ( y \leq z \Rightarrow Q ( x _ {1} \dots x _ {n} , y, z)) $$

or

$$ P ( x _ {1} \dots x _ {n} , z) \iff \ \exists y ( y \leq z \& Q ( x _ {1} \dots x _ {n} , y, z)). $$

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

Suppose that $ f _ {1} \dots f _ {s + 1 } $ are $ n $- place primitive recursive functions, and let $ P _ {1} \dots P _ {s} $ be primitive recursive relations such that for any set of argument values at most one of them is true. Then the function

$$ \tag{* } f ( x _ {1} \dots x _ {n} ) = \ \left \{ \begin{array}{ll} f _ {1} ( x _ {1} \dots x _ {n} ) &\textrm{ if } P _ {1} ( x _ {1} \dots x _ {n} ), \\ {} \dots \dots &{} \dots \dots \\ f _ {s} ( x _ {1} \dots x _ {n} ) &\textrm{ if } P _ {s} ( x _ {1} \dots x _ {n} ), \\ f _ {s + 1 } ( x _ {1} \dots x _ {n} ) &\textrm{ otherwise } , \\ \end{array} \right .$$

is primitive recursive.

One says that the function $ f ( x _ {1} \dots x _ {n} , z) $ has been obtained from an everywhere-defined function $ g ( x _ {1} \dots x _ {n} , y, z) $ by means of the bounded minimization operator if $ f ( x _ {1} \dots x _ {n} , z) $ is equal to the minimal $ y $ such that $ y \leq z $ and $ g ( x _ {1} \dots x _ {n} , y, z) = 0 $, and is equal to $ z + 1 $ otherwise. The class of primitive recursive functions is closed under bounded minimization operators.

A function $ \Phi ( y, x _ {1} \dots x _ {n} ) $ is called universal for the class of $ n $- place primitive recursive functions if for each such function $ f ( x _ {1} \dots x _ {n} ) $ there is a natural number $ k $ such that

$$ f ( x _ {1} \dots x _ {n} ) = \ \Phi ( k, x _ {1} \dots x _ {n} ). $$

There exists a universal function for every $ n \geq 1 $, 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 $ R ( x _ {1} \dots x _ {n} ) $ can be represented as $ \exists y A ( y, x _ {1} \dots x _ {n} ) $, where $ A $ 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 $ f ( x _ {1} \dots x _ {n} ) $ there is an arithmetical formula $ F ( y, x _ {1} \dots x _ {n} ) $ such that for all natural numbers $ k _ {1} \dots k _ {n} , m $, the formula $ F ( \overline{m}\; , \overline{k}\; _ {1} \dots \overline{k}\; _ {n} ) $ is derivable in formal arithmetic if $ f ( k _ {1} \dots k _ {n} ) = m $, while $ \neg F ( \overline{m}\; , \overline{k}\; _ {1} \dots \overline{k}\; _ {n} ) $ is derivable if $ f ( k _ {1} \dots k _ {n} ) \neq m $. (Here $ \overline{k}\; _ {1} \dots \overline{k}\; _ {n} , \overline{m}\; $ are arithmetical terms reflecting the natural numbers $ k _ {1} \dots k _ {n} , m $ 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)