Basically, the class of functions definable by recursively building up arithmetic functions: addition, multiplication, exponentiation, tetration, etc. What's not allowed is to "diagonalize" a whole series of such functions to produce an even faster-growing one. Thus, the Ackermann function was proposed in 1928 as an example of a recursive function that's not primitive recursive, showing that PR is strictly contained in R.
Alternatively, the PR functions are exactly those functions that can be computed via programs in any reasonable, idealized ALGOL-like programming language where only definite loops are allowed, that is, loops where the number of iterations is specified before the loop starts (so FOR-loops are okay but not WHILE- or REPEAT-loops), and recursive calls are not allowed.
Alternatively, the PR functions are those functions whose termination can be proved by well-founded induction using an ordinal less than ωω. (There are other systems for higher ordinals. Notably, Gödel's System T is an extension of PR with higher-order functions, and it allows all functions whose termination can be proved by well-founded induction using an ordinal less than ε0, including Ackermann's function.)
An interesting difference is that PR functions can be explicitly enumerated, whereas functions in R cannot be (since otherwise the halting problem would be decidable). In this sense, PR is a "syntactic" class whereas R is "semantic."
On the other hand, we can "enumerate" any RE set by a PR function in the following sense: given an input (M,k), where M is a Turing machine and k is an integer, if M halts within k steps then output M; otherwise output nothing. Then the union of the outputs, over all possible inputs (M,k), is exactly the set of M that halt.
PR strictly contains ELEMENTARY.
Defined in [Sch16]. Let and where is applied to itself times. For example , , etc. Then define, , note that this has the same growth rate as where A is the Ackermann function. This class is equal to DTIME(Fω(p(n))) over all primitive-recursive functions p(n). The class remains unchanged if we replace DTIME with NTIME or DSPACE.
Strictly contains ELEMENTARY, Tower, and PR. Is strictly contained in R.
The relationship between this class and PR is analogous to the relationship between Tower and ELEMENTARY. That is, Ack contains problems "barely" outside of PR and, unlike PR, has complete problems.
The reachability problems for Petri nets [Ler22] and vector addition systems [CO22] are complete for this class under primitive recursive reductions, as well as the problem of navigating robots through a maze of gadgets with spawner and destroyer nodes [Ani+23].
Equals the union of DTIME(2n), DTIME(22n), DTIME(222n), and so on.
The class of decision problems solvable by a Turing machine. Often identified with the class of 'effectively computable' functions (the Church-Turing thesis).
Defined in [Tur36], [Chu41], and other seminal early papers.
Strictly contains PR, the primitive recursive functions (see [Kle71]).
Defined in [Sch16] as the union of DTIME(F3(p(n))) over all elementary functions p(n), where F3 is the third level of the fast growing hierarchy, i.e., the iterated exponential function. The author describes this as the class of problems that are not in ELEMENTARY but only barely so. Unlike ELEMENTARY and PR, which have no complete problems, Tower has several natural examples of complete problems (under elementary reductions). Specifically, the Star-Free Expression Equivalence (SFEq) problem is complete for this class, as is the satisfiability of the Weak Monadic Theory of One Successor (WS1S).
Strictly contains ELEMENTARY and is strictly contained in PR.
Note that the same class is obtained if DTIME is replaced by NTIME or DSPACE in the definition.
