Saturday, April 2, 2011

Graham's Number

Someone asked a question on the Physics Forums asking for an explanation of the largeness of this number, so doing some research this is what I came up with:

It is a number that is impossible to comprehend. Going by the articles on wikipedia covering Graham's number, Knuth's up-arrow notation, Conway's chained arrow notation, and tetration(power tower),

\begin{align*}G = g_{64} &= 3 \rightarrow 3 \rightarrow g_{63} \\ ... \\ g_{2} &= 3 \rightarrow 3 \rightarrow g_{1} \\ g_{1} &= 3 \rightarrow 3 \rightarrow 4 \end{align*}

$$g_{1}$$ is already insanely huge number.

\begin{align*} g_{1} &= 3 \uparrow\uparrow\uparrow\uparrow 3 \\ &= 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 3 \\ &= 3 \uparrow\uparrow\uparrow (3 \uparrow\uparrow 3 \uparrow\uparrow 3) \\ &= 3 \uparrow\uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow 3 \uparrow 3)) \\ &= 3 \uparrow\uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow 27)) \end{align*}

$$3 \uparrow 27 = 7625597484987$$, so $$3 \uparrow\uparrow (3 \uparrow 27)$$ is 3 exponentiated by itself 7625597484987 times. Another way to write that is $$^{7625597484987}3$$. That still doesn't come close to giving us the value of $$g_{1}$$.

We still have to compute $$3 \uparrow\uparrow\uparrow (^{7625597484987}3)$$, and all we will have accomplished is to have determined the number of $$\uparrow$$ for $$g_{2}$$. Considering how impossibly large $$g_{1}$$ seems to be when it's Knuth up-arrow notation had a measly 4 $$\uparrow$$, then imagine how $$g_{2}$$ must dwarf $$g_{1}$$ since it's Knuth up-arrow notation will have $$g_{1} \uparrow$$. Then that continues on, each step from $$g_{2}$$ to $$g_{64}$$ being unbelievably larger than the previous step.