In
computability theory, a primitive recursive function is roughly speaking a function that can be computed by a
computer program whose
loops 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 functions that are also
total functions.
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 and
division, 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.
Definition
The primitive recursive functions are among the number-theoretic functions, which are functions from the
natural numbers (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
axioms:
More complex primitive recursive functions can be obtained by applying the
operations 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 values (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 loops or IF-THEN plus
GOTO, are admitted in a primitive recursive language.
Douglas Hofstadter's
BlooP in ''
Gödel, Escher, Bach'' is such a language. Adding unbounded loops (WHILE, GOTO) makes the language
general recursive and
Turing-complete, 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 is
indecidable 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.
Examples
Most number-theoretic functions definable using
recursion on a single variable are primitive recursive. Basic examples include the addition and
truncated subtraction functions.
Addition
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.
Subtraction
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(''n'', pred(''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''
11(''x''),
: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
Exponentiation and
primality testing 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 numberings, the primitive recursive functions can be extended to operate on other objects such as integers and
rational numbers. 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 (k
0, k
1, …, k
n), there are natural numbers b and c such that, for every i ≤ n, β(b, c, i) = k
i. We may thus use the following formula to define ''h''; more precisely, ''m''=''h''(''n'') is a shorthand for the following:
: