Fast as (insert word here) boi

You guessed it: fast-growing hierarchy!

On Wikipedia and the Googology Wikia, it’s complicated and long and boring and zzZZZZZZ… so I’ll try my best to simplify it.

Define a function, f0(n) = n + 1. It doesn’t grow so fast, does it?

For fa(n), that is fa-1n(n), where that denotes doing the previous function n times.

f1(n) would equal out to 2n, because iterating f0(n) n times would just be adding n to n, or 2n.

f2(n) is also iterating f1(n) n times, which is doubling each time, so it would equal out to 2nn.

I’ll do a couple more.

f3(n) is… its lower bound is 2nn((2(2^n)n)↑↑(n−1)).

f4(n) has a lower bound of f3(n)↑↑↑n.

After the finite ordinals, comes ω, the ordinal infinity. To find a fast-growing f function faster than the g function for Graham’s number, or the TREE function, we need to involve ω.

Let’s think of a table of f functions:

f1(1) = 2f1(2) = 4f1(3) = 6f1(4) = 8
f2(1) = 2f2(2) = 8f2(3) = 24f2(4) = 64
f3(1) = 2f3(2) = 2048f3(3) = According to Numberphile,
a number with 121 million digits
f3(4) = uyefwgiefwugewf
f4(1) = 2f4(2) = WTFf4(3) = Just no.f4(4) = Let’s not?
The table of fast-growing hierarchy!

The following information is provided originally from Numberphile.

Think of the diagonal from the upper-left corner, descending south-east. It’s faster than any function that came before it. fω(n) is that diagonal, so:

fω(n) = fn(n)

It has a lower bound of 2↑n-1n, which is also the single-argument Ackermann function defined by Harvey Friedman.

The next step? ω + 1. fω+1(n) just does the same thing, so fωn(n). Why is fω(n) and fω+1(n) different? Because ω is an ordinal infinity, where order matters, unlike cardinals.

fω+1(n) is HUGE. It’s iterating fω(n) n times, which is so huge. Its lower bound is {n, n, 1, 2} in Bird’s Array Notation.

Interesting fact: Googol is between f2(323) and f2(324).Another one: an approximation for Graham’s number is fω+1(64). For TREE? Uhh… if you want to know, it’s in the next post about fast-growing hierarchy.


One thought on “Fast as (insert word here) boi

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.