In computability theory
, a primitive recursive function is roughly speaking a function that can be computed by a computer program
are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset
of those general recursive function
s that are also total function
The importance of primitive recursive functions lies on the fact that most computable functions that are studied in number theory
(and more generally in mathematics) are primitive recursive. For example, addition
, the factorial
and exponential function
, and the function which returns the ''n''th prime are all primitive recursive. In fact, for showing that a computable function is primitive recursive, it suffices to show that its computational complexity
is bounded above by a primitive recursive function of the input size. It follows that it is difficult to devise a computable function
that is ''not'' primitive recursive, although some are known (see below).
The set of primitive recursive functions is known as PR
in computational complexity theory
The primitive recursive functions are among the number-theoretic functions, which are functions from the natural number
s (nonnegative integers) to the natural numbers. These functions take ''n'' arguments for some natural number ''n'' and are called ''n''-ary
The basic primitive recursive functions are given by these axiom
More complex primitive recursive functions can be obtained by applying the operation
s given by these axioms:
Example. We take ''f''(''x'') as the ''S''(''x'') defined above. This f is a 1-ary primitive recursive function. And so is ''g''(''x'') = ''S''(''x''). So ''h''(''x'') defined as ''f''(''g''(''x'')) = ''S''(''S''(''x'')) is a primitive recursive 1-ary function too. Informally speaking, ''h''(''x'') is the function that turns ''x'' into ''x''+2.
Example. Suppose ''f''(''x'') = ''P''11
(''x'') = ''x'' and ''g''(''x'',''y'',''z'')= ''S''(''P''23
(''x'',''y'',''z'')) = ''S''(''y''). Then ''h''(0,''x'') = ''x'' and ''h''(''S''(''y''),''x'') = ''g''(''y'',''h''(''y'',''x''),''x'') = ''S''(''h''(''y'',''x'')). Now ''h''(0,1) = 1, ''h''(1,1) = ''S''(''h''(0,1)) = 2, ''h''(2,1) = ''S''(''h''(1,1)) = 3. This ''h'' is a 2-ary primitive recursive function. We can call it 'addition'.
Interpretation. The function ''h'' acts as a for loop
from 0 up to the value of its first argument. The rest of the arguments for ''h'', denoted here with ''x''''i''
’s (''i'' = 1, ..., ''k''), are a set of initial conditions for the For loop which may be used by it during calculations but which are immutable by it. The functions ''f'' and ''g'' on the right side of the equations which define ''h'' represent the body of the loop, which performs calculations. Function ''f'' is only used once to perform initial calculations. Calculations for subsequent steps of the loop are performed by ''g''. The first parameter of ''g'' is fed the “current” value of the For loop’s index. The second parameter of ''g'' is fed the result of the For loop’s previous calculations, from previous steps. The rest of the parameters for ''g'' are those immutable initial conditions for the For loop mentioned earlier. They may be used by ''g'' to perform calculations but they will not themselves be altered by ''g''.
The primitive recursive functions are the basic functions and those obtained from the basic functions by applying these operations 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
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 value
s (that is ''t'' for true and ''f'' for false), or that produce truth values as outputs. 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 always 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
, where there is a known or calculable upper bound to all loops (FOR i FROM 1 TO n, with neither i nor n modifiable by the loop body). No control structures of greater generality, such as while loop
s or IF-THEN plus GOTO
, are admitted in a primitive recursive language. Douglas Hofstadter
in ''Gödel, Escher, Bach
'' is such a language. Adding unbounded loops (WHILE, GOTO) makes the language general recursive
, as are all real-world computer programming languages.
The definition of primitive recursive functions implies that their computation halts on every input (after a finite number of steps). On the other hand, the halting problem
for general recursive functions, even if they are total
. That is, there are programs that halt on every input, but for which this can not be verified by an algorithm.
Most number-theoretic functions definable using recursion
on a single variable are primitive recursive. Basic examples include the addition and truncated subtraction
Intuitively, addition can be recursively defined with the rules:
To fit this into a strict primitive recursive definition, define:
Here S(''n'') is "the successor of ''n''" (i.e., ''n''+1), ''P''11
is the identity function
, and ''P''23
is the projection function
that takes 3 arguments and returns the second one. Functions ''f'' and ''g'' required by the above definition of the primitive recursion operation are respectively played by ''P''11
and the composition of ''S'' and ''P''23
Because primitive recursive functions use natural numbers rather than integers, and the natural numbers are not closed under subtraction, a truncated subtraction function (also called "proper subtraction") is studied in this context. This limited subtraction function sub(''a'', ''b'') r ''b'' ∸ ''a''
returns ''b'' - ''a'' 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''12
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''11
:sub(S(''n''), ''x'') = pred(''P''23
(''n'', sub(''n'', ''x''), ''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 operations on natural numbers
and primality test
ing are primitive recursive. 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 numbering
s, the primitive recursive functions can be extended to operate on other objects such as integers and 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
operations are all primitive recursive.
Use in first-order Peano arithmetic
In first-order Peano arithmetic
, there are infinitely many variables (0-ary symbols) but no k-ary
non-logical symbols with k>0 other than S, +, *, and ≤. Thus in order to define primitive recursive functions one has to use the following trick by Gödel.
By using a Gödel numbering for sequences
, for example Gödel's β function
, any finite sequence of numbers can be encoded by a single number. Such a number can therefore represent the primitive recursive function until a given n.
Let ''h'' be a 1-ary primitive recursion function defined by:
where C is a constant and ''g'' is an already defined function.
Using Gödel's β function, for any sequence of natural numbers (k0
, …, kn
), there are natural numbers b and c such that, for every i ≤ n, β(b, c, i) = ki
. We may thus use the following formula to define ''h''; more precisely, ''m''=''h''(''n'') is a shorthand for the following: