Primitive recursive function

In computability theory, primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. They are defined using recursion and composition as central operations and are a strict subset of the recursive functions, which are exactly the computable functions. The broader class of recursive functions are defined by additionally allowing partial functions and introducing an unbounded search operator.

Related Topics:
Computability theory - Recursion - Composition - Subset - Recursive function - Computable function - Partial function

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Many of the functions normally studied in number theory, and approximations to real-valued functions, are primitive recursive, such as addition, division, factorial, exponential, finding the nth prime, and so on (Brainerd and Landweber, 1974). In fact, it is difficult to devise a function that is not primitive recursive, although some are known (see e.g. Ackermann function). Thus, by studying them, we can discover properties that have wide-reaching consequences.

Related Topics:
Number theory - Addition - Division - Factorial - Exponential - Ackermann function

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Primitive recursive functions can be computed by machines that always halt, while recursive functions require Turing-complete systems.

Related Topics:
Machines that always halt - Turing-complete

~ ~ ~ ~ ~ ~ ~ ~ ~ ~