Pardon me for asking a question whose answer is surely well-known, butis beyond my expertise:Q. Is the growth rate of each primitive recursive function $f(n)$ bounded by some exponential $O(c^n)$, or $O(n^n)$, or ...?I know Ackermann's function grows faster than exponential, but it is not primitive recursive.
Growth rate of primitive recursive functions
recursion;recursive
The answer is no, there is no exponential bound on PR.PR contains Knuth's up-arrow functions, Elementary functions, etc.PR is equal to the union of Grzegorczyk hierarchy.Exponential functions appear at the third level of the Grzegorczyk hierarchy.PR can alternatively be defined using the iteration function in place of recursion.A good reference for information about these classes is the first chapter of second volume of Classical Recursion Theory.Also have the general function growth hierarchies like Grzegorczyk hierarchy,slow-growing hierarchy, andfast-growing hierarchy.