PR is the complexity class of all primitive recursive functions—or, equivalently, the set of all formal languages that can be decided in time bounded by such a function. This includes addition, multiplication, exponentiation, tetration, etc.
The Ackermann function is an example of a function that is not primitive recursive, showing that PR is strictly contained in R (Cooper 2004:88).
On the other hand, we can "enumerate" any recursively enumerable set (see also its complexity class RE) by a primitive-recursive function in the following sense: given an input ( M , k ) {\displaystyle (M,k)} , where M {\displaystyle M} is a Turing machine and k {\displaystyle k} is an integer, if M {\displaystyle M} halts within k {\displaystyle k} steps then output M {\displaystyle M} ; otherwise output nothing. Then the union of the outputs, over all possible inputs ( M {\displaystyle M} , k {\displaystyle k} ), is exactly the set of M {\displaystyle M} that halt.
PR strictly contains ELEMENTARY.
PR does not contain "PR-complete" problems (assuming, e.g., reductions that belong to ELEMENTARY).
Hierarchy
The PR class can be divided into an infinite hierarchy of increasingly large complexity levels, according to the fast-growing hierarchy.
The 𝐅 0 {\displaystyle {\text{𝐅}}_{0}} class is the class of problems that can be solved in n + O ( 1 ) {\displaystyle n+O(1)} time. That is, there exists a Turing machine and a constant C {\displaystyle C} , such that given an input of length n {\displaystyle n} , the machine solves it and halts within n + C {\displaystyle n+C} steps.
The 𝐅 1 {\displaystyle {\text{𝐅}}_{1}} class is the class of problems that can be solved in p o l y ( n ) {\displaystyle {\mathsf {poly}}(n)} time.
The 𝐅 2 {\displaystyle {\text{𝐅}}_{2}} class is ELEMENTARY.
The 𝐅 3 {\displaystyle {\text{𝐅}}_{3}} class is TOWER, which can be equivalently written as the class of problems that can be solved in tetration-time.
The union ⋃ n ∈ N 𝐅 n {\displaystyle \bigcup _{n\in \mathbb {N} }{\text{𝐅}}_{n}} is PR.
In practice, many problems that are not in PR but just beyond it are 𝐅 ω {\displaystyle {\text{𝐅}}_{\omega }} -complete (Schmitz 2016).
- S. Barry Cooper (2004). Computability Theory. Chapman & Hall. ISBN 1-58488-237-9.
- Herbert Enderton (2011). Computability Theory. Academic Press. ISBN 978-0-12-384-958-8.
- Schmitz, Sylvain (2016). "Complexity Hierarchies beyond Elementary". ACM Transactions on Computation Theory. 8: 1–36. arXiv:1312.5686. doi:10.1145/2858784. S2CID 15155865.