5
$\begingroup$

Pardon me for asking a question whose answer is surely well-known, but is 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.

$\endgroup$
  • $\begingroup$ I am also not an expert but I am pretty sure that towers of exponents, and maybe even $2\uparrow^k n$ for any constant $k$ are primitive recursive en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation. $\endgroup$ – Sasho Nikolov Feb 6 '16 at 3:30
  • 1
    $\begingroup$ Actually, after googling something on a hunch, it seems that for every primitive recursive function $f(n)$ there exists a constant $k$ such that $f(n) \le A(n,k)$, where $A$ the Ackermann function. $\endgroup$ – Sasho Nikolov Feb 6 '16 at 3:37
12
$\begingroup$

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, and fast-growing hierarchy.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.