SEE ALSO: The Slow-growing Hierarchy
The fast-growing hierarchy (FGH for short) is a certain hierarchy mapping ordinals α (below the supremum μ of a fixed system of fundamental sequences) to a set of functions, which generated from fast-growing functions denoted by
f_α:N→N. For large ordinals α, f_α may grow very rapidly.
Due to its simple and clear definition, as well as its origins in professional mathematics, FGH is a popular benchmark for large number functions.
So we start with...
f_0(n) = n+1
f_0(f_0(n)) = n+2
f_1(n) = 2n
f_1(f_1(n)) = 4n
f_2(n) = (2^n)*n
f_2(f_2(n)) = (2^((2^n)*n)*(2^n)*n = 2^(((2^n)*n)+n)*n > 2^2^n
f_3(n) > 2^2^2^... n 2's ...2^2^((2^n)*n) > 2^2^2^... n 2's...2^2^2^n > 2^^n
f_4(n) > 2^^2^^2^^... n 2's ...2^^2^^2^^n > 2^^^n
...
Here I'll use w for what should be ω because its easier to type.
f_w(n) > 2{n-1}n
f_w(f_w(n)) > 2{2{n-1}n - 1}n > 2{2{n-1}n}n > 2{2{2}2}2 = 2{{1}}3
f_w+1(n) > 2{{1}}n+1 = 2{2{2{...2{2{2}2}2...}2}2}2 = 2{2{2{...2{4}2...}2}2}2 = 2{2{2{...4...}2}2}2
f_w+1(f_w+1(n)) > 2{{1}}2{{1}}n+1
Just a minute, 2{anything}2 = 4. we'll use another way to approximate this
f_w(n) > 2{n-2}2{n-2}2{n-2}... n 2's ...2{n-2}2{n-2}2{n-2}n > 2{n-1}n
let's invent a temporary notation [b,lp,p,k] so that BEAF {b,p,k} = our [b,b,p,k]
(for now we'll assume n > 2, what is the point of analysing n <= 3)
so f_w(n) > [2,n,n,n-1] > 2{n-1}n = {2,n,n-1}
f_w(f_w(n)) > [2,[2,n,n,n-1],[2,n,n,n-1],[2,n,n,n-1]-1]
ok we have no choice but to change to ANOTHER BASE for better approximations. remember we have n>2.
>2{n-1}n will mean >2{n-1}3 and we all know that 3{a}2 >= 2{a}3 for a >= -1.
We simply cannot hold onto the precision much longer. after some calculation we can safely say:
f_w+1(n) > {n,n,1,2}
f_w+2(n) > {n,n,2,2}
(you get the idea)
f_w2(n) > {n,n,n,2}
f_w2(f_w2(n)) > {n,n,{n,n,n,2},2} = {n,3,1,3}
You might be thinking, (if you did not read about the ordinals yet), why are we writing w2 and not 2w?
Think of it this way: think of 2. now think of having infinity of them. you can believe it's infinity.
NOW think of infinity. its MUCH harder to think that, if you multiply this by 2, you get infinity.
Really controversial and paradoxic but just believe that w2 is correct and not a typo.
...
f_w2+1(n) > {n,n+1,1,3}
f_w2+2(n) > {n,n+1,2,3}
...
f_w3(n) > {n,n+1,n,3}
f_w4(n) > {n,n+1,n,4}
f_w5(n) > {n,n+1,n,5}
...
f_w^2(n) > {n,n+1,n,n}
f_w^2+1(n) > {n,n+1,1,1,2}
... ...
f_w^2*2(n) > {n,n+1,n,n,2}
f_w^2*3(n) > {n,n+1,n,n,3}
...
f_w^3(n) > {n,n+1,n,n,n}
f_w^4(n) > {n,n+1,n,n,n,n}
f_w^5(n) > {n,n+1,n,n,n,n,n}
...
f_w^w(n) > {n,n+2(1)2}
f_(w^w)*2)(n) > {n,n+2(1)3}
...
f_w^(w+1)(n) > {n,n+2(1)n+1}
f_w^(w+1)+1(n) > {n+1,n+1(1)1,2}
...
f_w^(w+2)(n) > {n,n(1)n,n}
f_w^(w+3)(n) > {n,n(1)n,n,n}
...
f_w^(w2)(n) > {n,n(1)(1)2}
f_w^(w3)(n) > {n,n(1)(1)(1)2}
...
f_w^(w^2)(n) > {n,n(2)2}
f_w^(w^3)(n) > {n,n(3)2}
...
as you can see FGH is MUUUUCH faster than SGH, we barely reached w^w^w and we already reached SUPERDIMENSIONAL ARRAYS. we can fast-forward to...
f_epsilon_0(n) > X^^X & n-1
now beaf is bad defined but most of us use THAT as our main notation, ok we will use approximation
f_zeta_0(n) ~ X^^X^2 & n
f_eta_0(n) ~ X^^X^3 & n
... ... ...
f_gamma_0(n) ~ X^^^X & n
f_phi(w,0,0)(n) ~ {X,X,X} & n = 3 & X & n
f_phi(1,0,0,0)(n) ~ {X,X,1,2} & n
Now what happens when we reach the ordinal phi(...,0,0,0,0,0,0)? that's for another time :P