Primitive recursive function
In computability theory, primitive recursive functions are a class of functions that are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions (µ-recursive functions are also called partial recursive).
Primitive recursive functions form an important building block on the way to a full formalization of computability. These functions are also important in proof theory.
Most of the functions normally studied in number theory are primitive recursive. For example: addition, division, factorial, exponential and the nth prime are all primitive recursive. So are many approximations to real-valued functions.
In fact, it is difficult to devise a total recursive function that is not primitive recursive, although some are known.
The set of primitive recursive functions is known as PR in computational complexity theory.
See also
- Computability theory
- Computable function
- Computational complexity theory
- Course-of-values recursion
- Double recursion
- Function composition
- Grzegorczyk hierarchy
- Μ-recursive_function
- Machine that always halts
- Primitive recursive functional
- Primitive recursive ordinal function
- Primitive recursive set function
- Recursion (computer science)
- Total function
External links
- Primitive recursive function @ Wikipedia