Primitive recursive function

Primitive recursive functions are total functions from simple basic functions (constant 0 function, projections to an argument and successor function) composition and (primitive ) recursion can be formed. The term primitive recursive function was coined by the Hungarian mathematician Rózsa Péter. Primitive recursive functions play in recursion, a branch of theoretical computer science, a role. They occur in connection with the explication of the concept of computability.

All primitive recursive functions are computable in the intuitive sense. But you draw from, not all intuitively computable functions, examples of which are the Ackermann function and the Sudan function, both of which are computable but not primitive recursive. A complete coverage of the concept of predictability is possible only by the μ - recursive functions.

For primitive recursive functions, it is possible to define a complexity measure, ie, the duration of the calculation of their function values ​​are determined in advance.

The class of primitive recursive functions and the LOOP - computable (see LOOP - program ) functions are equivalent.

Definition

The set of primitive recursive functions is then defined as the smallest set containing all zero functions, all projections and the successor function, and which is closed under composition and primitive recursion. Everyday words this means: A function is primitive recursive if and only if one can write down an expression to the said means. Even as a primitive recursive proven functions may happen in the expression, as they can indeed be eliminated by substituting its expression.

Each k- digit primitive recursive function is particularly always defined on all of. Functions with a smaller domain must only be continued suitable to all, so as to obtain primitive recursive functions.

Examples

Addition

Addition is defined recursively by

For everyone. It is therefore, the addition is so primitive recursive.

Multiplication

The multiplication is defined recursively via the addition:

For everyone. The multiplication is primitive recursive, because it is.

Potency

The potency with the meaning is defined recursively on the multiplication:

For everyone. The potency is primitive recursive, because it is. The context here has the purpose of the two parameters m and n to exchange with each other.

Predecessor function

The previous function is not defined at the point 0. So it is not primitive recursive. By continuing at the point 0, for example, with the value 0 can, however, make a primitive recursive function of it.

The modified predecessor function defined by

For all is primitive recursive, because it is.

Subtraction

The subtraction is not defined on all pairs of natural numbers. So you set the subtraction by padding with zeros away completely. This total subtraction can be characterized recursively by

For everyone. For the total subtraction; she is so primitive recursive. Man calls this modified differential also arithmetic difference.

Other examples

• The two -digit and functions are primitive recursive.
• The sequence of prime numbers is a primitive recursive function.
• The function to be a natural number and a prime number, the number of prime factors of determined is primitive recursively.
• There are primitive recursive Arithmetisierungen finite sequences of natural numbers.
• The Ackermann function and the Sudan function is not primitive recursive, but μ - recursive.
• The function Hardworking beaver (busy beaver ) is not primitive recursive and non - recursive μ.