Introduction to Googology

The googology is the study of large/enormous numbers!
"What is a big number?" could you say. Well, a "large number" is defined as any number bigger than... 1. That avoid many problems :/
But how far could we go? How big can we make a number growth without using infinity and with mathematical methods?
For example we have the "famous" large numbers called the Googol. Many people thinks that it is the "largest" number (wich is a non-sense), while it is only 10¹⁰⁰. How can we get bigger? 10¹⁰¹⁰⁰, aka the "googolplex" vastly exceeds it. Can we beat a googolplex? 10^1010100, aka "googolduplex" beat it. Can we beat any -plex number? Of course! Let's just define this function P:

P(0) = 10¹⁰⁰ = googol
P(1) = 10¹⁰¹⁰⁰ = googolplex
P(2) = 10^1010100 = googolduplex
P(3) = 10^101010100 = googoltriplex
P(n) = 10^P(n-1)

So, what would be P(P(2))? It would be 10^1010...100 with a googolduplex "10" powers!!!
Big enough? NO.

F(n) = Pⁿ(n) = P(P(P(P(...P(n)...)))) is incredibly faster!
F(1) = P(1)
F(2) = P(P(2))
F(5) = P(P(P(P(P(5)))))
etc.

F grows much faster than P. We say that "F eventually dominates P" (or "P is eventually dominated by F") and note it F(n) > P(n).

But... what is the fastest-growing function ever defined? We are going to see lots of functions until we find the fastest :-D

1) Donald Knuth's up-arrow notation!

Category: primitive recursive
Growth rate: f_ω(n) <==> f_n(n) < n↑ⁿn < f_n+1(n) (fast-growing hiearchy -- I will explain what this it in a further lesson)

Okay, its time to talk about the up-arrow notation!!!

Here are the rules:
a↑¹b = a^b
a↑ⁿ1 = a
a↑ⁿ⁺¹(b+1) = a↑ⁿ(a↑ⁿ⁺¹b)

I explain:

3↑3 = 3³ = 27
3↑↑3 = 3↑(3↑3) = 3⁽³³⁾ = 3²⁷ ~= 7.6255975x10¹²
3↑↑↑3 = 3↑↑(3↑↑3) = 3↑↑(7.6255975x10¹²) = 3^333...3 with 7.6255975x10¹² powers!! The power tower reaches venus!!!
3↑↑↑↑3 = 3↑↑↑(3↑↑↑3) = 3↑↑↑(3↑↑(7.6255975x10¹²)) = 3^333...3 with a number of powers equal to 3^33...3 with a number of powers equal to 3^333...3, etc. You continue adding power towers 3↑↑(7.6255975x10¹²) times and get an incredibly huge number!!!

More generally, a(↑ⁿ)b = a↑↑...n arrows..↑↑b

The Ackerman function A(n) = n↑ⁿn is known because it eventually dominates any primitive-recursive function!! (every function with a fix arrow number)

2) Graham's Function

Category: recursive
Growth rate: f_ω+1(n)

The Graham's Function is an extremely fast-growing function defined by the following:

G(0) = 4
G(n+1) = 3(↑^G(n))3

Wich means that G(1) = 3↑↑↑↑3, and G(2) = 3↑↑↑↑...(3↑↑↑↑3) arrows...↑↑↑↑3 wich is ENORMOUS!!!

Graham's Number is the solution to a Graph Theory problem formuled by Ron Graham. It is one of the largest numbers with an utility and is about G64!!!!

3) Forcal Function (Aarex's Graham Generator)

Category: recursive
Growth rate: Forcal_a,b(n) < f_ω+(b+2)(n)

Rule 1: When a=1 and b=1:
-> Forcal₁(n) = G(Forcal₁(n-1)) (G stands for Graham's function)

Rule 2. When n=0:
-> Forcal_#(0) = 1000000

Rule 3. a=1 and b>1:
-> Forcal_1,b(n) = Forcal_{Forcal1,b(n-1),b-1}(1)

Rule 4. No subscripts:
-> Forcal(n) = Forcal₁(n)

Rule 5. Rules 1-4 don't apply:
-> Forcal_{a #}(n) = Forcal_{a-1 #}(Forcal_{a #}(n-1))

Pretty powerful function!

Let's Gⁿ(k) = G(G(G(G(...G(k)...))))) with n layers

Forcal(n) = Gⁿ(10⁶) -- already very fast!
Forcal₂(n) = G^Gn(1)(10⁶)
Forcal₃(n) = G^GGn(1)(106)(10⁶)
Forcal_a(n) = G^{GG...Gn(1)(106)(106)}(10⁶) with a stages!!!
I will do Forcal_a,b(n) later ;-(

4) Conway's Chained arrow notation



[under construction]