[FOM] Frank's elegant solution

[Toby Ord]

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.