[FOM] Frank's elegant solution

[JoeShipman@aol.com]

f(x) = 2^x/2^1 + 2^2^x/2^2^2 + 2^2^2^x/2^2^2^3 + 2^2^2^2^x/2^2^2^2^4 + ...
answers my query for a naturally defined real function which dominates any function with a finite stack of 2's. The key point is that for any x, all but finitely many terms are vanishingly small. (Matt Frank's idea. slightly simplified by me.)

This construction gives us a real function which dominates any function with a finite stack of exponents.  It is clear it can be generalized to dominate any given primitive recursive function, but I don't see how to get past the Ackermann barrier.

The construction only gives a function with large enough growth.  It does not interpolate directly a function commonly defined by induction.

If f is absolutely monotonic, an alternative construction is to construct successive "functional square roots" g(g(x))=f(x), h(h(x))=g(x), etc., by working directly with formal power series.  This allows one to define "x-fold composition" of a function where x is any dyadic rational, not just an integer, and extend to all reals x by continuity, but also seems limited to primitive recusive functions.  (Need a "canonical" way to solve g(g(x))=h(x) here.) 

-- JS