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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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