# Is there any function that like this function?

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

• I think this is very close to being the Ackermann function – Q the Platypus May 10 '18 at 6:32
• Thank you, Could you show that this function can be write in term of Ackermann function ? – Ro Theory May 10 '18 at 9:38
• For integer $a$, there would be some expression with Knuth's up-arrow notation. For ordinal $a$, I got no idea how fast will this grow... – didgogns May 10 '18 at 13:18

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$$

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.