Lets say: $G=\text{Graham's Number}$.
$$ \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!!

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


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.