Question about $TREE(3)$ and Graham's Number

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

• Is the choice of $\beta_{\beta_{G}}$ arbitrary or did you choose this specific value for a reason? – aidangallagher4 Aug 13 '18 at 13:14
• How do you define $\beta_n$? – Simply Beautiful Art Aug 13 '18 at 13:20
• Sidenote: this is likely much smaller than $\operatorname{TREE}(3)$ for the same reason as your previous question. – Simply Beautiful Art Aug 13 '18 at 13:55
• @SimplyBeautifulArt, I add the the answer to my question, I hope it's much clear now :) – CS1 Aug 13 '18 at 14:40
• See also: Golf a number larger than TREE(3) – Simply Beautiful Art Aug 14 '18 at 19:20

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.