show/hide this revision's text 2 Improved exposition; added 171 characters in body

I interpret the question as asking whether it

The class of primitive recursive functions is the casesmallest class of functions containing the basic primitive recursive functions (zero, successor, whenever we define a projection) and closed under the two operations:

  • composition: if $h$ and $g_1,\ldots,g_k$ are primitive recursive, so is the function $f$ by $\vec x\mapsto h(g_1(\vec x),g_2(\vec x),\ldots,g_k(\vec x)).$$
  • primitive recursion: if $h$ and composition, using prior known $g$ are primitive recursivefunctions , then so is the function $g_0,g_1,\ldots,g_n$, f$ defined by $$f(0,\vec x)=h(\vec x),$$ $$f(n+1,\vec x)=g(n,\vec x, f(n,\vec x)).$$

    • This class is extremely robust and includes all of the functions that you mention in your question (but it falls short of the class of all Turing computable functions). I interpret your question as being about the extent to which we might also express $f$ explicitly as a term in hope to eliminate the language having function symbols for those recursion scheme, and still arrive at the same class of functions$g_i$.

    With this interpretation.

    One easy observation, of course, is that we cannot simply eliminate the answer recursion scheme as is noand still get all primitive recursive functions. For example, even if we may add addition and multiplication as basic functions, then the composition scheme will remain inside the class of polynomial functions. But we can easily define exponentiation the exponential function $n\mapsto 2^n$ by recursion over that class, and this does not have polynomial growth.

    More generally, let us consider whether we might add finitely many additional, powerful primitive recursive application functions $g_1,\ldots,g_k$ as basic, and then close only under composition. This interpretation of multiplicationthe question would be: can we arrange that this class is closed under definition by recursion? In other words, but any single is every function definable by recursion using those functions and their compositions already expressible as a term in the language using only multiplication has at most polynomial growth, and therefore will not give rise to exponentiation.

    More generallythose functions (that is, in as a composition)?

    The answer to this more robust context, suppose we have general version of the question is still no. For any finitely many primitive recursive functions $g_1,\ldots,g_k$, including the basic primitive recursive functions (closure of it under composition is strictly smaller than the zero function, successor closure of it under composition and projection)definition by recursion. In this caseSpecifically, there will still be another a primitive recursive function $f$, defined by one or more recursions over those $g_i$, g_i$ and the usual basic functions, which has a higher growth rate than any individual term in those functions. For example, this This can be proved by using a high enough level function $A_n$ of the Ackermann function, because whenever a collection of functions is dominated by $A_n$, then all terms in those functions are dominated by $A_{n+1}$.
    show/hide this revision's text 1

    I interpret the question as asking whether it is the case, whenever we define a function $f$ by recursion and composition, using prior known primitive recursive functions $g_0,g_1,\ldots,g_n$, that we might also express $f$ explicitly as a term in the language having function symbols for those functions $g_i$.

    With this interpretation, the answer is no. For example, we may easily define exponentiation $2^n$ by recursive application of multiplication, but any single term in the language using only multiplication has at most polynomial growth, and therefore will not give rise to exponentiation.

    More generally, in a more robust context, suppose we have finitely many primitive recursive functions $g_1,\ldots,g_k$, including the basic primitive recursive functions (the zero function, successor and projection). In this case, there will still be another primitive recursive function $f$, defined by one or more recursions over those $g_i$, which has a higher growth rate than any individual term in those functions. For example, this can be proved by using a high enough level function $A_n$ of the Ackermann function, because whenever a collection of functions is dominated by $A_n$, then all terms in those functions are dominated by $A_{n+1}$.