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

  • 2
    $\begingroup$ I think this is very close to being the Ackermann function $\endgroup$ – Q the Platypus May 10 '18 at 6:32
  • $\begingroup$ Thank you, Could you show that this function can be write in term of Ackermann function ? $\endgroup$ – Ro Theory May 10 '18 at 9:38
  • $\begingroup$ 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... $\endgroup$ – 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


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



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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.