2
$\begingroup$

How is the number

$$\large f_{\omega^3}(2)$$

in the fast growing hierarchy calculated ?

My only idea is to convert to

$$\large f_{\omega^2 2}(2)$$

but now I have no idea how to continue.

$\endgroup$
  • $\begingroup$ Which fast-growing hierarchy? There are several... $\endgroup$ – Steven Stadnicki May 4 '14 at 20:59
3
$\begingroup$

Too large to calculate!

I assume you are referring to the definition on Wikipedia: http://en.wikipedia.org/wiki/Fast-growing_hierarchy

If so, then, as the article points out, $f_{\omega + 1}(64)$ is already larger than Graham's number. $f_{\omega^3}$ is much larger than this.

But perhaps you're asking what an algorithm could be if we have unbounded time and space? Well here's a start:

$f_{\omega^3}(2) = f_{\omega^2 \cdot 2}(2) = f_{\omega^2 + \omega^2}(2) = f_{\omega^2 + \omega \cdot 2}(2) = f_{\omega^2 + \omega + \omega}(2) = f_{\omega^2 + \omega + 2}(2) = f_{\omega^2 + \omega + 1}^2(2) = f_{\omega^2 + \omega + 1}(f_{\omega^2 + \omega + 1}(2)) = f_{\omega^2 + \omega + 1}(f_{\omega^2 + \omega}^2(2)) = f_{\omega^2 + \omega +1}(f_{\omega^2 + \omega}(f_{\omega^2 + \omega}(2))) = f_{\omega^2 + \omega +1}(f_{\omega^2 + \omega}(f_{\omega^2 + 2}(2))) = f_{\omega^2 + \omega +1}(f_{\omega^2 + \omega}(f_{\omega^2 + 1}(f_{\omega^2 + 1}(2)))) = f_{\omega^2 + \omega +1}(f_{\omega^2 + \omega}(f_{\omega^2 + 1}(f_{\omega^2}(f_{\omega^2}(2))))) = f_{\omega^2 + \omega +1}(f_{\omega^2 + \omega}(f_{\omega^2 + 1}(f_{\omega^2}(f_{\omega + \omega}(2))))) = f_{\omega^2 + \omega +1}(f_{\omega^2 + \omega}(f_{\omega^2 + 1}(f_{\omega^2}(f_{\omega + 2}(2))))) = f_{\omega^2 + \omega +1}(f_{\omega^2 + \omega}(f_{\omega^2 + 1}(f_{\omega^2}(f_{\omega + 1}(f_{\omega + 1}(2)))))) = f_{\omega^2 + \omega +1}(f_{\omega^2 + \omega}(f_{\omega^2 + 1}(f_{\omega^2}(f_{\omega + 1}(f_{\omega}(f_{\omega}(2))))))) = f_{\omega^2 + \omega +1}(f_{\omega^2 + \omega}(f_{\omega^2 + 1}(f_{\omega^2}(f_{\omega + 1}(f_{\omega}(8)))))) = f_{\omega^2 + \omega +1}(f_{\omega^2 + \omega}(f_{\omega^2 + 1}(f_{\omega^2}(f_{\omega + 1}(f_8(8)))))) = ...$

At this point I get bored of writing this out by hand, but you get the point, you just keep applying the rules. At some point the numbers will get too large to write down.

Why do you ask about calculating this number?

$\endgroup$
  • $\begingroup$ I was only curious, if $\large f_{\omega^3}(2)$ is already larger than expressions in conway-chains. I tried once more and got the same solution. Thanks for your efforts though. It is clear that the number cannot be described with conway chains. $\endgroup$ – Peter May 5 '14 at 12:10
  • $\begingroup$ @Peter If that was your intention, see here: googology.wikia.com/wiki/List_of_functions $\endgroup$ – Simply Beautiful Art Mar 6 '17 at 1:57
2
$\begingroup$

In fast growing hierarchy, we always break our limit ordinals into their fundamental sequences and diagonolize. This is a lengthy process, but it should be intuitive. We start with the definition of $\omega$ as the limit of the following sequence:

$$\omega=\{1,2,3,\ldots\}$$

$\omega[2]$ would then be the second term in the fundamental sequence, which would be two. We define $\omega\cdot2$ by the following sequence:

$$\omega\cdot2=\omega+\omega=\{\omega+1,\omega+2,\omega+3,\ldots\}$$

Anyways, for your ordinal:

$$\omega^3=\{\omega^2,\omega^2\cdot2,\omega^2\cdot3,\ldots\}$$

And so you correctly had $\omega^3[2]=\omega^2\cdot2$. Then,

$$\omega^2\cdot2=\omega^2+\omega\cdot\omega=\{\omega^2+\omega,\omega^2+\omega\cdot2,\omega^2+\omega\cdot3,\ldots\}$$

Thus, $\omega^2\cdot2 [2]=\omega^2+\omega\cdot2$. From there we break $\omega\cdot2 [2]=\omega+2$, and then we finally have a successor ordinal, and thus we expand as

$$\begin{align}f_{\omega^3}(2)&=f_{\omega^2+\omega+1}(f_{\omega^2+\omega+1}(2))\\&=f_{\omega^2+\omega+1}(f_{\omega^2+\omega}(f_{\omega^2+\omega}(2)))\end{align}$$

And now we have a limit ordinal again, so expand some more.

Also, we usually diagonalize starting with the smallest ordinal when taking a sum of ordinals.

$\endgroup$

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.