Primitive recursive function

related topics
{math, number, function}

The primitive recursive functions 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). The term was coined by Rózsa Péter.

In computability theory, primitive recursive functions are a class of functions that 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. (Brainerd and Landweber, 1974) In fact, it is difficult to devise a function that is not primitive recursive, although some are known (see the section on Limitations below). The set of primitive recursive functions is known as PR in complexity theory.

Every primitive recursive function is a general recursive function.

Contents

Definition

Full article ▸

related documents
Continuous function
Dual space
Euler's formula
Convolution
Fundamental theorem of algebra
Basis (linear algebra)
BCH code
Ackermann function
Hyperreal number
Fundamental group
Computable number
Bessel function
Multivariate normal distribution
Halting problem
Dynamic programming
Fermat number
Lp space
Prime number theorem
Probability theory
Group action
Abelian group
Subset sum problem
Monte Carlo method
Permutation
Factorial
Uniform space
Truth table
Frame problem
Taylor series
Support vector machine