Magnitude of Graham’s Number?

I recently stumbled across this number, and then (foolishly, most likely) decided to try to describe it in a blog post

http://frothygirlz.com/2010/01/14/big-numbers-part-2/

Q - Are there any comparisons of Graham's Number, hell, even G1, to other well known "big" numbers, such as googolplex?

I'd just like to have some way, however abstract, to be able to pretend that I have some sort of idea of the magnitude of this number.

Any help and/or tips would be much appreciated.

-
(just added the soft-question tag) – Zev Chonoles Jan 15 2010 at 23:24
Your blog entry is quite well-written. I liked it a lot. It was real fun. Although, it is not of the usual type of questions MO spends time on, or I have encountered in grad school. – Anweshi Jan 16 2010 at 1:56
I once saw the results of a fascinating competition: the entries consisted of C programs of at most 2000 bytes, and the object was to write a program which would output the largest number. The competition was theoretical; "int" was assumed to allow arbitrarily large integers (which C does not), memory and time were assumed unlimited, and the only rule was that programs were required to eventually terminate. Unforunately I could not find the link, but the results were mind-boggling. – Frank Thorne Dec 18 at 18:48
arxiv.org/abs/1304.6910 "Graham's Number is Less Than 2^^^6" by Mikhail Lavrov, Mitchell Lee, John Mackey. – Andres Caicedo Apr 27 at 2:06

I think all that can really be said is that a googolplex is much, much smaller.

This isn't a direct comparison of a googolplex with Graham's number, but maybe it will help give some perspective:

Some back-of-the-envelope/Mathematica calculations tell me that

$10^{(10^{100})}\approx 3^{(3^{(3^{4.86})})}$

and so a googolplex is between $3\uparrow\uparrow 4=3^{(3^{(3^{3})})}$ and $3\uparrow\uparrow 5=3^{(3^{(3^{27})})}$ (much closer to $3\uparrow\uparrow 4$, obviously).

-

Graham's number is truly amazing, so big that it's easy to underestimate it. Gerhard Paseman has seriously underestimated how big Graham's number is in terms of the Ackermann function. A(m,n)=2↑(m-2)(n+3)-3. So the first step of the Graham's function, 3↑↑↑↑3 = g1, is very roughly A(6,6). The second step g2 is roughly A(g1,g1) and the actual Graham's number, g64, is roughly A(g63,g63). That's how big Graham's number is.

You can also use the iterated function notation with the Ackermann function to approximate Graham's number more concisely. First define A(n)=A(n,n). Then Graham's number is roughly A64(4). That's A(A(A...A(4)...) with 64 A's. A number so large that you have to apply Ackermann's function to 4, take that result, plug it back in until you've done it 64 times! So n(3) in Friedman's paper referenced above is far smaller than Graham's number, even with the improved lower bound of A(7198, 158386) from theorem 8.3 in the same paper. However n(4) in that same sequence has a lower bound of AA(187196)(1). Think about that. The number of times you have to plug the intermediate result back into the Ackermann function to get n(4) is so large that it has to be described with the Ackermann function itself! It makes Graham's number seem tiny.

TREE(3) is so much bigger then those numbers that it hurts my brain to think about it. So I won't.

-
 Indeed. Thanks for making it more explicit. At least only the index for n() was off by 1. – Gerhard Paseman Feb 21 2010 at 4:50 Thank you Lexivore ~ Now I need to go back and brush up on Ackermann functions! – Robert Feb 22 2010 at 14:11

Here's a link that may be of interest: http://www.scottaaronson.com/writings/bignumbers.html

-

Such numbers are best understood in terms of some computability hierarchy. A common starting point is Ackermann's function, a version of which grows faster than any primitive recursive function (i.e. any fortran function definable with for loops, successor, and unlimited resources) . I will let you look up the function so that I do not misstate its definition. A(4,4) is something like the number of quarks in the universe, A(5,5) the number of arrangements of such quarks, and Graham's number is something like A(6,6). (I am making these up. Check elsewhere for the actual numbers. The above is just to give you an idea of scale.)

EDIT: Another poster has fixed the idea of scale, showing that Graham's number is much larger than I represent above. That poster also goes on to mention n(4) from the article mentioned below is in turn much larger than Graham's number which is much larger than n(3). END EDIT

However, Graham's number is near the beginning of a list of enormous numbers. Harvey Friedman has a paper on some nice combinatorial problems whose answers go far beyond Graham's number. One of them is a simple sequence problem which starts out something like 2, 12, B, where B is somewhere near A(300,300). If more details come to mind, I will post them here.

In fact, I will post a section from Friedman's paper, 'Enormous Integers in Real Life'. He asked several people to guess at the size of B, which in the quote below is n(3), including L. Lovasz, given the description of the sequence. Lovasz guessed 20,000; Friedman uses A(n) instead of A(n,n):

"THEOREM 8.2. n(3) > A(7,184).

Lovasz wins, as his guess is closer to A(7,184) than the other guesses. "

-
 Wikipedia has an example of a larger number here (linked from theys Graham's number page): en.wikipedia.org/wiki/… – Ilya Grigoriev Jan 25 2010 at 4:29 Lexivore has posted a response which makes a place in Friedman's Ackermann hierarchy for Graham's number. Perhaps a complexity ranking list in a similar fashion will develop and be posted somewhere. – Gerhard Paseman Feb 21 2010 at 5:01

I realize this thread is from a year and a half ago (a possible spam post moved it into the current thread titles), but if anyone is still interested in these issues, about 9 years ago I posted in sci.math a lengthy essay on Graham's number and then followed it up with three more essays (and a promise for more, which I never got around to).

GRAHAM'S NUMBER AND RAPIDLY GROWING FUNCTIONS [2 March 2002] http://groups.google.com/group/sci.math/msg/0f3c8bab92145996

BIG NUMBERS #1 [8 April 2002] http://groups.google.com/group/sci.math/msg/403051f310ff3dfc

BIG NUMBERS #2 [8 April 2002] http://groups.google.com/group/sci.math/msg/d12962e3af2c74b7

BIG NUMBERS #3 [8 April 2002] http://groups.google.com/group/sci.math/msg/4f2ed8e0385b72f2

-

Here's one way to put it:

3↑↑3 = 3^(3^3) ~= 7.6 trillion

3↑↑↑3 = 3↑↑(3↑↑3) = 3↑↑(7.6 trillion). Let's start calculating this number:

3↑↑4 = 3^(7.6 trillion) ~= 10^(3.6 trillion) > a google

3↑↑5 = 3^(10^3.6 trillion) ~= 10^(0.477 * 10^3.6 trillion) > a googleplex

Now - take this to the 7.6 trillionth power of 3. 3↑↑↑3 makes a gooogleplexian look like bus fare.

G1 = 3↑↑↑(3↑↑↑3).

And G2 = 3↑(G1 times)3

G1 is ridiculously large, and it just gets worse from there.

-

Thank you, both of you, for taking the time to answer. Both were helpful, and both were appreciated!

I downloaded Freidman's "Enormous Integers in Real Life", and am looking through it now. Gerhard, to your point, Friedman says early on, "...that A(5,5) is incomprehensibly large. We propose this number as a sort of benchmark." Can't wait to look through the rest of it!

Zev, appreciate the restating of a googolplex in up-arrow notation; wished I'd thought of doing it that way, as it really helps put it in perspective. That a googolplex is so infinitesimal compared to 3^^^3 is...staggering.

Thanks!

-