Difference between revisions of "Primitive recursive function"

Latest revision as of 07:45, 20 September 2016

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