Is there any function that like this function?

Question

I got a idea from fast-growing hierarchy function to create new function g.(I think it is computable.)

$$g_0(n) = n + 1$$

$$g_{a+1}(n) = g_a^{g_a(n)}(n)$$

Which different from fast-growing hierarchy function f.

$$f_0(n) = n + 1$$

$$f_{a+1}(n) = f_a^{n}(a)$$

Is there any function that like this function ?

And is it possible to write $g_a(n)$ = something in term of Knuth's up-arrow notation or Conway chained arrow notation ?

I think there is someone create this function or something like this function before. (In mathematical, I think it is impossible to create new thing if you have a little knowledge. I have a little knowledge about big number and

Answer 1

I'll prove $g_a(n)\ge Ack(a,n)$ by induction
Note: I use $A_m(n)=Ack(m,n)$

for $a=0$

$$g_0(n)=n+1\ge A_0(1)=n+1$$

for $a+1$

$$g_{a+1}(n)=g_{a}^{g^a(n)}(n)\ge g_a^{n+1}(n)>A^{n+1}_a(1)=A_{a+1}(n)$$

This is a fairly weak approximation but $g_a(n)$ should be smaller than $A_{a+1}(n)$ so it's not too bad.

Answer 2

I will be proving $g_a(n)\le f_{2a}(n)$ for all $n>1$ by induction.

---

For $a=0$, the two are equal.

---

For $a=k+1$, let $h_a(n)=g_a^n(n)$. Assume $n\le g_k(n)\le f_{2k}(n)$.

Note that $h_k(n)\le f_{2k}^n(n)=f_{2k+1}(n)$ and

\begin{align}g_{k+1}(n)&=g_k^{g_k(n)}(n)\\&<g_a^{g_a(n)}(g_a(n))\\&=h_k(g_a(n))\\&<h_k(h_k(n))\\&<h_k^n(n)\\&\le f_{2k+1}^n(n)\\&=f_{2(k+1)}(n)\end{align}

which concludes the proof that $g_a(n)\le f_{2a}(n)$ by induction.

As far as fast growing hierarchy bounds via the Knuth arrows, we have

$$2\uparrow^an<f_{a+1}(n)<2\uparrow^a2n$$

hence, combining with the obvious lower bound of $f_a(n)\le g_a(n)$, we get

$$2\uparrow^an<g_{a+1}(n)<2\uparrow^{2a+1}2n$$