Lets say: $G=\text{Graham's Number}$.
And:
$$
\begin{align*}
\alpha_1&=G\uparrow^G G, \\
\alpha_2&=\alpha_1\uparrow^{\alpha_1} \alpha_1 \\
&\vdots\\
\beta_1 &= \alpha_G\uparrow^{\alpha_G}\alpha_G \\
\beta_2 &= \beta_1 \uparrow^{\beta_1 }\beta_1 \\
\beta_n &= \beta_{n-1} \uparrow^{\beta_{n-1} }\beta_{n-1}
\end{align*}
$$
Then:
is $\beta_{\beta_G}$ still smaller then $TREE(3)$?
$a\uparrow^nb$ is Knuth's up-arrow notation
Thank you!!
Best Answer
This is much much smaller than $\operatorname{TREE}(3)$. To give you a rough taste, $G\approx f_{\omega+1}(64)$, and every application of $n\mapsto n\uparrow^nn$ only increases the inner argument by $1$, so $\alpha_n\approx f_{\omega+1}(64+n)$ and $\beta_n\approx f_{\omega+1}(64+G+n)\approx f_{\omega+1}(f_{\omega+1}(64)+64+n)$.
On the other hand, we have $f_{\omega+2}(n)=\overbrace{f_{\omega+1}(f_{\omega+1}(f_{\omega+1}(\dots f_{\omega+1}(}^nn)\dots)))$, so already $f_{\omega+2}(4)>\beta_{\beta_G}$.
In general,
$$f_{\alpha+1}(n)=\overbrace{f_\alpha(f_\alpha(f_\alpha(\dots f_\alpha(}^nn)\dots)))$$
so we likely have $f_{\omega+3}(3)=f_{\omega+2}(f_{\omega+2}(f_{\omega+2}(3)))$ to be much greater than your number.
On the other hand, $\operatorname{TREE}(n)\gtrapprox f_{\vartheta(\Omega^\omega\omega)}(n)$, which is significantly larger.
As a brief explanation of the fast growing hierarchy for a few more ordinals, we have
$$f_0(n)=n+1\\f_1(n)=2n\\f_2(n)=n2^n\\f_k(n)\gtrapprox2\uparrow^{k-1}n\\f_\omega(n)=f_n(n)\approx n\uparrow^nn\\f_{\omega2}(n)=f_{\omega+n}(n)\\f_{\omega k}(n)=f_{\omega(k-1)+n}(n)\\f_{\omega^2}(n)=f_{\omega n}(n)\\\vdots$$
In comparison, $\vartheta(\Omega^\omega\omega)\gg\omega^{\omega^{\omega^{.^{.^.}}}}\gg\omega^\omega\gg\omega^2$, which isn't anywhere near close to a good approximation to $\vartheta(\Omega^\omega\omega)$, which should tell you how frightening large this is.
For some introductions to the fast growing hierarchy, I recommend watching David Metzler's videos or Giroux Studio's videos, and checking out my chatroom.