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, f₀(n) = n + 1. It doesn’t grow so fast, does it?

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

f₁(n) would equal out to 2n, because iterating f₀(n) n times would just be adding n to n, or 2n.

f₂(n) is also iterating f₁(n) n times, which is doubling each time, so it would equal out to 2ⁿn.

I’ll do a couple more.

f₃(n) is… its lower bound is 2ⁿn((2^{(2^n)n})↑↑(n−1)).

f₄(n) has a lower bound of f₃(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) = 2	f1(2) = 4	f1(3) = 6	f1(4) = 8	…
f2(1) = 2	f2(2) = 8	f2(3) = 24	f2(4) = 64	…
f3(1) = 2	f3(2) = 2048	f3(3) = According to Numberphile, a number with 121 million digits	f3(4) = uyefwgiefwugewf	…
f4(1) = 2	f4(2) = WTF	f4(3) = Just no.	f4(4) = Let’s not?	…
…	…	…	…	…

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) = f_n(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). 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 f₂(323) and f₂(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