# 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:

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.

Bye

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

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