[1] In fact, for showing that a computable function is primitive recursive, it suffices to show that its time complexity is bounded above by a primitive recursive function of the input size.
[2] It is hence not particularly easy to devise a computable function that is not primitive recursive; some examples are shown in section § Limitations below.
The set of primitive recursive functions is known as PR in computational complexity theory.
, to compute the sum of its arguments, can be obtained using the primitive recursion operator
To this end, the well-known equations are "rephrased in primitive recursive function terminology": In the definition of
As a computation example, The limited subtraction function (also called "monus", and denoted "
As a computation example, In some settings it is natural to consider primitive recursive functions that take as inputs tuples that mix numbers with truth values (that is
for false),[citation needed] or that produce truth values as outputs.
[4] This can be accomplished by identifying the truth values with numbers in any fixed manner.
Such an identification of predicates with numeric functions will be assumed for the remainder of this article.
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.
Most also appear with similar names, either as proofs or as examples, in Boolos, Burgess & Jeffrey (2002, pp.
63–70) they add the logarithm lo(x, y) or lg(x, y) depending on the exact derivation.
The functions 16–20 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 numbers.
The broader class of partial recursive functions is defined by introducing an unbounded search operator.
An equivalent definition states that a partial recursive function is one that can be computed by a Turing machine.
While all primitive recursive functions are provably total, the converse is not true.
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.
This argument can be applied to any class of computable (total) functions that can be enumerated in this way, as explained in the article Machine that always halts.
Gladstone[8] improved this so that even the combination of these two restrictions, i.e., the pure iteration rule below, is enough: Further improvements are possible: Severin[9] prove that even the pure iteration rule without parameters, namely suffices to generate all unary primitive recursive functions if we extend the set of initial functions with truncated subtraction x ∸ y.
Definitions in these forms may be easier to find or more natural for reading or writing.
No control structures of greater generality, such as while loops or IF-THEN plus GOTO, are admitted in a primitive recursive language.
A variant of the LOOP language is Douglas Hofstadter's BlooP in Gödel, Escher, Bach.
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 undecidable for general recursive functions.
For example, Gödel's incompleteness theorem can be formalized into PRA, giving the following theorem: 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.
For example, many consistency results in set theory that are obtained by forcing can be recast as syntactic proofs that can be formalized in PRA.
This work was the first to give a proof that a certain recursive construction defines a unique function.
The current terminology was coined by Rózsa Péter (1934) after Ackermann had proved in 1928 that the function which today is named after him was not primitive recursive, an event which prompted the need to rename what until then were simply called recursive functions.