[FOM] Frank's elegant solution
Toby Ord
toby at amirrorclear.net
Tue Oct 21 20:12:27 EDT 2003
On Tuesday, October 21, 2003, at 06:12 am, JoeShipman at aol.com wrote:
> 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.)
In this vein, what about:
h(x) = x/1 + (2^^2)^x/(2^^2)^2 + (3^^^3)^x/(3^^^3)^3 + ...
where n^^m = n^n^n^n^...^n {m times}
and n^^^m = n^^n^^n^^n^^...^^n {m times}
and so on.
We can define the Ackermann function as
A(i,j,k) = j^^^^...^^^^k {with i _arrows_}
Now, h(x) = Sum_n A(n,n,n)^(x-n)
so when x exceeds n+1, h(x) exceeds A(n,n,n).
To avoid this +1 business, we could have
h2(x) = Sum_n A(n,n,n)^(x-n+1)
but it is of no consequence: h(x) grows faster than all primitive
recursive functions.
We could use
g(x) = Sum_n S(n)^(x-n)
where S(n) is Rado's busy beaver function for a particularly fast rate
of growth, or use whatever function from N to N you want.
We now seem to have everything one could want in terms of growth and a
fairly simple formula, but a generalisation of a common function at the
integer points is still lacking.
Toby.
More information about the FOM
mailing list