# Growth rate of primitive and $\mu$-recursive functions

Functions that are not primitive recursive but $\mu$-recursive are said to grow too fast to be primitive recursive.

Are there functions $f$ and $F$ such that a function is primitive recursive iff its growth rate is less than $f$'s and $\mu$-recursive only iff its growth rate is greater than $F$'s?

Is there a function $G$ such that a function with growth rate greater than $G$'s isn't computable at all, i.e. not even $\mu$-recursive?

-

The answer to your first question is "no". There are non-recursive functions that only take values 0 and 1. For example, take the characteristic function of a non-recursive set.

Even if you restrict your question to functions that are strictly increasing, the answer is still no, for very similar reasons: You can have a function $f$ that is not recursive but $f(n+1)-f(n)=1$ or $2$ for all $n$. For example, start with a non-recursive set, and let $f(n+1)-f(n)-1$ be the characteristic function of that set.

What is true is that there are functions $f,F$ such that any primitive recursive function grows slower than $f$ and any recursive function grows slower than $F$. Any version of Ackermann's function is an example of the first phenomenon. An example of the second can be obtained easily as follows: First, note that there are only countably many recursive functions. List them as $f_1,f_2,\dots$, and let $F(n)=\sum_{i\le n}f_i(n)+1$.

There is actually quite a bit of literature around these issues. The partial order of functions $f:{\mathbb N}\to{\mathbb N}$ ordered by eventual domination (i.e., $f<g$ iff $f(n)<f(n)$ for all but finitely many $n$) has been extensively studied in set theory. The argument in the paragraph above is simply that its "cofinality" is not countable. The sizes of the least collection of functions such that any function is dominated by one of them, or no function dominates all of them, are well known "cardinal characteristics of the continuum", in this case the numbers ${\mathfrak d}$ and ${\mathfrak b}$, respectively. These are uncountable numbers, less than or equal than the size of the reals. A very good reference for them is Andreas Blass article for the "Handbook of set theory", "Combinatorial Cardinal Characteristics of the Continuum". It should be available from his homepage.

The study of hierarchies of fast-growing functions is essential in proof theory. For example, if certain recursive function grows like Ackermann's function, then if a theory can only "see" primitive recursive functions, then it won't be able to "see" this function. Here, a theory "sees" a recursive function iff it can prove that the function is total. Hence, if a statement implies that, say, Ackermann's function is defined for all values, that means that the statement cannot be provable in the theory in question.

A concrete example is so-called Primitive Recursive Arithmetic. Similarly, we can associate to Peano arithmetic a recursive function $f_{\epsilon_0}$ that dominates all recursive functions that Peano arithmetic sees. Many famous examples of incompleteness (mathematical statements about natural numbers that cannot be proved "finitistically") were obtained by showing that the statements in question imply that certain recursive functions grow as $f_{\epsilon_0}$ or faster.

A good reference for these matters is the article by Fairtlough and Wainer in the "Handbook of Proof Theory", "Hierarchies of provably recursive functions".

For a very nice concrete example, I highly recommend the paper by Ketonen and Solovay, "Rapidly growing Ramsey functions", The Annals of Mathematics 113, 2 (1981), 267–314. They study one of these statements that is true but not provable in Peano arithmetic (the Paris-Harrington theorem) by analyzing the rate of growth of functions naturally associated to it and relating them to one of the standard hierarchies (the one Fairtlough and Wainer denote $F_\alpha$).

A natural related question is whether in some sense Ackermann's function is the smallest recursive function that dominates all primitive recursive functions. The answer to this is also no. A very recent reference is the article by Simmons, "The Ackermann functions are not optimal but by how much?" J. Symbolic Logic 75 (2010), no. 1, 289–313.

-
Thanks a lot for this comprehensive answer: it gives me more than I would have expected - and quite a bit reading! –  Hans Stricker Apr 7 '11 at 9:32
Glad I could help. –  Andres Caicedo Apr 7 '11 at 15:21

There is a fair bit of literature on functions $G$ which grow faster than any $\mu$-recursive function. Usually one considers instead infinite subsets of the non-negative integers which are very "sparse" in the sense that the gap between successive elements grows faster than any recursive function. For details, you could search for the term "hyper-immune." Maybe add "recursive function" to avoid the magic drug sites.

-

AFAIK the answer to the very first portion of your question (is there a function $f$ such that a function is primitive recursive iff its growth rate is less than $f$'s) is no, for an instructive reason: the inverse Ackermann function isn't primitive recursive, any more than the Ackermann function itself is. In general, while growing sufficiently fast is a sufficient condition for a function to be outside a particular 'recursion class', it's virtually never a necessary one.

-