Primitive recursive function - AbsoluteAstronomy.com

The primitive recursive functions are defined using primitive recursion

Recursion (computer science)

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. The approach can be applied to many types of problems, and is one of the central ideas of computer science....

and composition

Function composition

In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...

as central operations and are a strict subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

of the total µ-recursive functions (µ-recursive functions are also called partial recursive

Computable function

Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...

). The term was coined by Rózsa Péter

Rózsa Péter

Rózsa Péter , Hungarian name Péter Rózsa, was a Hungarian mathematician. She is best known for her work with recursion theory....

.

In computability theory

Recursion theory

Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...

, primitive recursive functions are a class of functions

Function (mathematics)

In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

that form an important building block on the way to a full formalization of computability. These functions are also important in proof theory

Proof theory

Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...

.

Most of the functions normally studied in number theory

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

are primitive recursive. For example: addition

Addition

Addition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....

, division

Division (mathematics)

right|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...

, factorial

Factorial

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...

, exponential

Exponential function

In mathematics, the exponential function is the function ex, where e is the number such that the function ex is its own derivative. The exponential function is used to model a relationship in which a constant change in the independent variable gives the same proportional change In mathematics,...

and the nth prime are all primitive recursive. So are many approximations to real-valued functions. 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

PR (complexity)

PR is the complexity class of all primitive recursive functions – or, equivalently, the set of all formal languages that can be decided by such a function...

in complexity theory

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

.

Every primitive recursive function is a general recursive function.

Definition

The primitive recursive functions are among the number-theoretic functions, which are functions from the natural number

Natural number

In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s (nonnegative integers) {0, 1, 2 , ...} to the natural numbers. These functions take n arguments for some natural number n and are called n-ary

Arity

In logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...

.

The basic primitive recursive functions are given by these axiom

Axiom

In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...

Constant function: The 0-ary constant function
Constant term
In mathematics, a constant term is a term in an algebraic expression has a value that is constant or cannot change, because it does not contain any modifiable variables. For example, in the quadratic polynomialx^2 + 2x + 3,\ the 3 is a constant term....

0 is primitive recursive.
Successor function: The 1-ary successor function S, which returns the successor of its argument (see Peano postulates), is primitive recursive. That is, S(k) = k + 1.
Projection function: For every n≥1 and each i with 1≤i≤n, the n-ary projection function P_iⁿ, which returns its i-th argument, is primitive recursive.

More complex primitive recursive functions can be obtained by applying the operation

Operation (mathematics)

The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation....

s given by these axioms:

Composition: Given f, a k-ary primitive recursive function, and k m-ary primitive recursive functions g₁,...,g_k, the composition
Function composition
In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...

of f with g₁,...,g_k, i.e. the m-ary function is primitive recursive.
Primitive recursion: Given f, a k-ary primitive recursive function, and g, a (k+2)-ary primitive recursive function, the (k+1)-ary function h is defined as the primitive recursion of f and g, i.e. the function h is primitive recursive when

and

The primitive recursive functions are the basic functions and those obtained from the basic functions by applying the operators a finite number of times.

Role of the projection functions

The projection functions can be used to avoid the apparent rigidity in terms of the arity

Arity

of the functions above; by using compositions with various projection functions, it is possible to pass a subset of the arguments of one function to another function. For example, if g and h are 2-ary primitive recursive functions then

is also primitive recursive. One formal definition using projection functions is

Converting predicates to numeric functions

In some settings it is natural to consider primitive recursive functions that take as inputs tuples that mix numbers with truth values { t= true, f=false }, or that produce truth values as outputs (see Kleene [1952 pp. 226–227]). This can be accomplished by identifying the truth values with numbers in any fixed manner. For example, it is common to identify the truth value t with the number 1 and the truth value f with the number 0. Once this identification has been made, the characteristic function of a set A, which literally returns 1 or 0, can be viewed as a predicate that tells whether a number is in the set A. Such an identification of predicates with numeric functions will be assumed for the remainder of this article.

Computer language definition

An example of a primitive recursive programming language is one that contains basic arithmetic operators (e.g. + and -, or ADD and SUBTRACT), conditionals and comparison (IF-THEN, EQUALS, LESS-THAN), and bounded loops, such as the basic for loop

For loop

In computer science a for loop is a programming language statement which allows code to be repeatedly executed. A for loop is classified as an iteration statement....

, where there is a known or calculable upper bound to all loops (FOR i FROM 1 to n), and no more general control structures such as while loop

While loop

In most computer programming languages, a while loop is a control flow statement that allows code to be executed repeatedly based on a given boolean condition. The while loop can be thought of as a repeating if statement....

s or IF-THEN plus GOTO

Goto

goto is a statement found in many computer programming languages. It is a combination of the English words go and to. It performs a one-way transfer of control to another line of code; in contrast a function call normally returns control...

. Douglas Hofstadter's

Douglas Hofstadter

Douglas Richard Hofstadter is an American academic whose research focuses on consciousness, analogy-making, artistic creation, literary translation, and discovery in mathematics and physics...

Bloop in Gödel, Escher, Bach

Gödel, Escher, Bach

Gödel, Escher, Bach: An Eternal Golden Braid is a book by Douglas Hofstadter, described by his publishing company as "a metaphorical fugue on minds and machines in the spirit of Lewis Carroll"....

is one such. Adding unbounded loops (WHILE, GOTO) makes the language partially recursive, or Turing-complete; Floop is such, as are almost all real-world computer languages.

Arbitrary computer programs, or Turing machines, cannot in general be analyzed to see if they halt or not (the halting problem

Halting problem

In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...

). However, all primitive recursive functions halt. This is not a contradiction; primitive recursive programs are a non-arbitrary subset of all possible programs, constructed specifically to be analyzable.

Examples

Most number-theoretic functions definable using recursion

Recursion (computer science)

on a single variable are primitive recursive. Basic examples include the addition and "limited subtraction" functions.

Addition

Intuitively, addition can be recursively defined with the rules:

add(0,x)=x,

add(n+1,x)=add(n,x)+1.

To fit this into a strict primitive recursive definition, define:

add(0,x)=P₁¹(x) ,

add(S(n),x)=S(P₁³(add(n,x),n,x)).

Here P₁³ is the projection function that takes 3 arguments and returns the first one.

P₁¹ is simply the identity function

Identity function

In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument...

; its inclusion is required by the definition of the primitive recursion operator above; it plays the role of f. The composition of S and P₁³, which is primitive recursive, plays the role of g.

Subtraction

Because primitive recursive functions use natural numbers rather than integers, and the natural numbers are not closed under subtraction, a limited subtraction function is studied in this context. This limited subtraction function sub(a,b) returns

if this is nonnegative and returns 0 otherwise.

The predecessor function acts as the opposite of the successor function and is recursively defined by the rules:

pred(0)=0,

pred(n+1)=n.

These rules can be converted into a more formal definition by primitive recursion:

pred(0)=0,

pred(S(n))=P₂²(pred(n),n).

The limited subtraction function is definable from the predecessor function in a manner analogous to the way addition is defined from successor:

sub(0,x)=P₁¹(x),

sub(S(n),x)=pred(P₁³(sub(n,x),n,x)).

Here sub(a,b) corresponds to b-a; for the sake of simplicity, the order of the arguments has been switched from the "standard" definition to fit the requirements of primitive recursion. This could easily be rectified using composition with suitable projections.

Other primitive recursive functions include exponentiation

Exponentiation

Exponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent n...

and primality test

Primality test

A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not...

ing. Given primitive recursive functions e, f, g, and h, a function that returns the value of g when e≤f and the value of h otherwise is primitive recursive.

Operations on integers and rational numbers

By using Gödel numberings, the primitive recursive functions can be extended to operate on other objects such as integers and rational number

Rational number

In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...

s. If integers are encoded by Gödel numbers in a standard way, the arithmetic operations including addition, subtraction, and multiplication are all primitive recursive. Similarly, if the rationals are represented by Gödel numbers then the field

Field (mathematics)

In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...

operations are all primitive recursive.

Relationship to recursive functions

The broader class of partial recursive functions is defined by introducing an unbounded search operator

Mu operator

In computability theory, the μ operator, minimization operator, or unbounded search operator searches for the least natural number with a given property.- Definition :...

. The use of this operator may result in a partial function

Partial function

In mathematics, a partial function from X to Y is a function ƒ: X' → Y, where X' is a subset of X. It generalizes the concept of a function by not forcing f to map every element of X to an element of Y . If X' = X, then ƒ is called a total function and is equivalent to a function...

, that is, a relation with at most one value for each argument, but does not necessarily have any value for any argument (see domain

Domain (mathematics)

In mathematics, the domain of definition or simply the domain of a function is the set of "input" or argument values for which the function is defined...

). An equivalent definition states that a partial recursive function is one that can be computed by a Turing machine

Turing machine

A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...

. A total recursive function is a partial recursive function that is defined for every input.

Every primitive recursive function is total recursive, but not all total recursive functions are primitive recursive. The Ackermann function

Ackermann function

In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive...

A(m,n) is a well-known example of a total recursive function that is not primitive recursive. There is a characterization of the primitive recursive functions as a subset of the total recursive functions using the Ackermann function. This characterization states that a function is primitive recursive if and only if

If and only if

In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....

there is a natural number m such that the function can be computed by a Turing machine that always halts within A(m,n) or fewer steps, where n is the sum of the arguments of the primitive recursive function.

An important property of the primitive recursive functions is that they are a recursively enumerable subset of the set of all total recursive functions (which is not itself recursively enumerable). This means that there is a single computable function f(e,n) such that:

For every primitive recursive function g, there is an e such that g(n) = f(e,n) for all n, and
For every e, the function h(n) = f(e,n) is primitive recursive.

However, the primitive recursive functions are not the largest recursively enumerable set of total computable functions.

Limitations

Primitive recursive functions tend to correspond very closely with our intuition of what a computable function must be. Certainly the initial functions are intuitively computable (in their very simplicity), and the two operations by which one can create new primitive recursive functions are also very straightforward. However the set of primitive recursive functions does not include every possible total computable function – this can be seen with a variant of Cantor's diagonal argument

Cantor's diagonal argument

Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural...

. This argument provides a total computable function that is not primitive recursive. A sketch of the proof is as follows:

The primitive recursive functions can be computably enumerated

Recursively enumerable set

In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:...

. This numbering is unique on the definitions of functions, though not unique on the actual functions themselves (as every function can have an infinite number of definitions — consider simply composing by the identity function

Identity function

In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument...

). The numbering is computable in the sense that it can be defined under formal models of computability such as μ-recursive function

Mu-recursive function

In mathematical logic and computer science, the μ-recursive functions are a class of partial functions from natural numbers to natural numbers which are "computable" in an intuitive sense. In fact, in computability theory it is shown that the μ-recursive functions are precisely the functions that...

s or Turing machine

Turing machine

s; but an appeal to the Church-Turing thesis is likely sufficient.

Now consider a matrix where the rows are the primitive recursive functions of one argument under this numbering, and the columns are the natural numbers. Then each element (i, j) corresponds to the ith unary primitive recursive function being calculated on the number j. We can write this as f_i(j).

Now consider the function g(x) = S(f_x(x)). g lies on the diagonal of this matrix and simply adds one to the value it finds. This function is total and computable (by the above), but clearly no primitive recursive function exists that computes it as it differs from each possible primitive recursive function by at least one value. Thus there must be total computable functions that are not primitive recursive.

This argument can be applied to any class of computable (total) functions that can be enumerated in this way, as explained in the article Machines that always halt. Note however that the partial computable functions (those that need not be defined for all arguments) can be explicitly enumerated, for instance by enumerating Turing machine encodings.

Other examples of total recursive but not primitive recursive functions are known:

The function that takes m to Ackermann
Ackermann function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive...

(m,m) is a unary total recursive function that is not primitive recursive.
The Paris–Harrington theorem
Paris–Harrington theorem
In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory is true, but not provable in Peano arithmetic...

involves a total recursive function that is not primitive recursive. Because this function is motivated by Ramsey theory
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...

, it is sometimes considered more “natural” than the Ackermann function.
The Sudan function
Sudan function
In the theory of computation, the Sudan function is an example of a function that is recursive, but not primitive recursive. This is also true of the better-known Ackermann function. The Sudan function was the first function having this property to be published....

Some common primitive recursive functions

The following examples and definitions are from Kleene (1952) pp. 223-231 — many appear with proofs. Most also appear with similar names, either as proofs or as examples, in Boolos-Burgess-Jeffrey 2002 pp. 63-70; they add #22 the logarithm lo(x, y) or lg(x, y) depending on the exact derivation.

In the following we observe that primitive recursive functions can be of four types:

functions for short: "number-theoretic functions" from { 0, 1, 2, ...} to { 0, 1, 2, ...},
predicates: from { 0, 1, 2, ...} to truth values { t =true, f =false },
propositional connectives: from truth values { t, f } to truth values { t, f },
representing functions: from truth values { t, f } to { 0, 1, 2, ... }. Many times a predicate requires a representing function to convert the predicate's output { t, f } to { 0, 1 } (note the order "t" to "0" and "f" to "1" matches with ~(sig) defined below). By definition a function φ(x) is a "representing function" of the predicate P(x) if φ takes only values 0 and 1 and produces 0 when P is true".

In the following the mark " ' ", e.g. a' , is the primitive mark meaning "the successor of", usually thought of as " +1", e.g. a +1 =_def a'. The functions 16-21 and #G are of particular interest with respect to converting primitive recursive predicates to, and extracting them from, their "arithmetical" form expressed as Gödel number

Gödel number

In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was famously used by Kurt Gödel for the proof of his incompleteness theorems...

Addition: a+b
Multiplication: a×b
Exponentiation: a^b,
Factorial a! : 0! = 1, a'! = a!×a'
pred(a): Decrement: "predecessor of a" defined as "If a> 0 then a-1 → a_new else 0 → a."
Proper subtraction: a ┴ b defined as "If a ≥ b then a-b else 0."
Minimum (a₁, ... a_n)
Maximum (a₁, ... a_n)
Absolute value: | a-b | =_defined a ┴ b + b ┴ a
~sg(a): NOT[signum(a)]: If a=0 then sg(a)=1 else if a>0 then sg(a)=0
sg(a): signum(a): If a=0 then sg(a)=0 else if a>0 then sg(a)=1
"b divides a" [ a | b ]: If the remainder ( a, b )=0 then [ a | b ] else b does not divide a "evenly"
Remainder ( a, b ): the leftover if b does not divide a "evenly". Also called MOD(a, b)
a = b: sg | a - b |
a < b: sg( a' ┴ b )
Pr(a): a is a prime number Pr(a) =_def a>1 & NOT(Exists c)_{1 [ c|a ]}
P_i: the i+1-st prime number
(a)_i : exponent a_i of p_i =_def μx [ _{x [p_i^x|a & NOT(p_i ^x'|a ]; μx is the minimization operator described in #E below.}
lh(a): the "length" or number of non-vanishing exponents in a
a×b: given the expression of a and b as prime factors then a×b is the product's expression as prime factors
lo(x, y): logarithm of x to the base y

In the following, the abbreviation x =_def x_i, ... x_n; subscripts may be applied if the meaning requires.

#A: A function φ definable explicitly from functions Ψ and constants q₁ , ... q_n is primitive recursive in Ψ.
#B: The finite sum Σ_{y ψ(x, y) and product Π_{yψ(x, y) are primite recursive in ψ.}}
#C: A predicate P obtained by substituting functions χ₁ ,..., χ_m for the respective variables of a predicate Q is primitive recursive in χ₁ ,..., χ_m, Q.
#D: The following predicates are primitive recursive in Q and R:

NOT_Q(x) .
Q OR R: Q(x) V R(x),
Q AND R: Q(x) & R(x),
Q IMPLIES R: Q(x) → R(x)
Q is equivalent to R: Q(x) ≡ R(x)
- #E: The following predicates are primitive recursive in the predicate R:
(Ey)_{y R(x, y) where (Ey)_{y denotes "there exists at least one y that is less than z such that"}}
(y)_{y R(x, y) where (y)_{y denotes "for all y less than z it is true that"}}
μy_{y R(x, y). The operator μy_{y R(x, y) is a bounded form of the so-called minimization- or mu-operator: Defined as "the least value of y less than z such that R(x, y) is true; or z if there is no such value."

#F: Definition by cases: The function defined thus, where Q₁, ..., Q_m are mutually exclusive predicates (or "ψ(x) shall have the value given by the first clause that applies), is primitive recursive in φ₁, ..., Q₁, ... Q_m:}}

φ(x) =

φ₁(x) if Q₁(x) is true,
. . . . . . . . . . . . . . . . . . .
φ_m(x) if Q_m(x) is true
φ_m+1(x) otherwise
- #G: If φ satisfies the equation:

φ(y,x) = χ(y, NOT-φ(y; x₂, ... x_n ), x₂, ... x_n then φ is primitive recursive in χ. 'So, in a sense the knowledge of the value NOT-φ(y; x_{2 to n} ) of the course-of-values function is equivalent to the knowledge of the sequence of values φ(0,x_{2 to n}), ..., φ(y-1,x_{2 to n}) of the original function."

Additional primitive recursive forms

Some additional forms of recursion also define functions that are in fact
primitive recursive. Definitions in these forms may be easier to find or
more natural for reading or writing.

Course-of-values recursion defines primitive recursive functions.

Some forms of mutual recursion
also define primitive recursive functions.

Finitism and consistency results

The primitive recursive functions are closely related to mathematical finitism

Finitism

In the philosophy of mathematics, one of the varieties of finitism is an extreme form of constructivism, according to which a mathematical object does not exist unless it can be constructed from natural numbers in a finite number of steps...

, and are used in several contexts in mathematical logic where a particularly constructive system is desired. Primitive recursive arithmetic

Primitive recursive arithmetic

Primitive recursive arithmetic, or PRA, is a quantifier-free formalization of the natural numbers. It was first proposed by Skolem as a formalization of his finitist conception of the foundations of arithmetic, and it is widely agreed that all reasoning of PRA is finitist...

(PRA), a formal axiom system for the natural numbers and the primitive recursive functions on them, is often used for this purpose.

PRA is much weaker than Peano arithmetic, which is not a finitistic system. Nevertheless, many results in number theory

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

and in proof theory

Proof theory

can be proved in PRA. For example, Gödel's incompleteness theorem can be formalized into PRA, giving the following theorem:

If T is a theory of arithmetic satisfying certain hypotheses, with Gödel sentence G_T, then PRA proves the implication Con(T)→G_T.

Similarly, many of the syntactic results in proof theory can be proved in PRA, which implies that there are primitive recursive functions that carry out the corresponding syntactic transformations of proofs.

In proof theory and set theory

Set theory

Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

, there is an interest in finitistic consistency proof

Consistency proof

In logic, a consistent theory is one that does not contain a contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent if and only if it has a model, i.e. there exists an interpretation under which all...

s, that is, consistency proofs that themselves are finitistically acceptable. Such a proof establishes that the consistency of a theory T implies the consistency of a theory S by producing a primitive recursive function that can transform any proof of an inconsistency from S into a proof of an inconsistency from T. One sufficient condition for a consistency proof to be finitistic is the ability to formalize it in PRA. For example, many consistency results in set theory that are obtained by forcing

Forcing (mathematics)

In the mathematical discipline of set theory, forcing is a technique invented by Paul Cohen for proving consistency and independence results. It was first used, in 1963, to prove the independence of the axiom of choice and the continuum hypothesis from Zermelo–Fraenkel set theory...

can be recast as syntactic proofs that can be formalized in PRA.

Definition

Role of the projection functions

Converting predicates to numeric functions

Computer language definition

Examples

Addition

Subtraction

Operations on integers and rational numbers

Relationship to recursive functions

Limitations

Some common primitive recursive functions

Additional primitive recursive forms

Finitism and consistency results

See also