View source for Primitive recursive function

In [[computability theory]], '''primitive recursive functions''' are a class of [[Function (mathematics)|functions]] that are defined using primitive recursion and [[Function composition|composition]] as central operations and are a strict subset of the [[Total function|total]] [[Μ-recursive_function|µ-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 ==

* [https://en.wikipedia.org/wiki/Primitive_recursive_function Primitive recursive function] @ Wikipedia


[[Category:Computation]]
[[Category:Functions]]