Graham's Number

https://en.wikipedia.org/wiki/Graham%27s_number

by grhmc • 11 years ago

52 25 11 years ago

en.wikipedia.org

prezjordan• 11 years ago

My brain melts every time I watch this video [1] from Numberphile on Graham's number.

They also had another video [2] with Ron Graham himself :)

[1] https://www.youtube.com/watch?v=XTeJ64KD5cg [2]: https://www.youtube.com/watch?v=GuigptwlVHo

CurtMonash3• 11 years ago

It seems like the real character here is Graham, who I've never met, but I do have a story about his collaborator Bruce Rothschild, who was my professor for junior-level linear algebra.

In those days, you either gave your professors little self-addressed stamped postcards to tell you your grade, or went to their offices to ask them. I took the latter approach with Rothschild. "What grade were you expecting?", he replied. I confessed that I thought I would probably get an A. "You're getting an F", he said. "I'm giving everybody the opposite of what they expect."

formalsystem3• 11 years ago

I TA'd for Graham's Discrete math class at UCSD. He's still quite the character! His last lecture he juggled a handful of chalks in class and brought his deck of cards to do magic tricks.

He once made me pull out a 1$ bill from my pocket in his office and then asked me what the serial number was, he shot out a question like: "what's the probability that you have n consecutive numbers on the bill".

You could tell Math was legitimately fun for him, he treated open math problems like brain teasers and that fun rubbed off on the people around him as well.

teejae• 11 years ago

You were playing Liar's Poker.

pmelendez• 11 years ago

Was he joking?

formalsystem3• 11 years ago

He wasn't serious but he would have been interested in a quick answer. I didn't get it cause I couldn't think of a quick way to know what a reasonable upper bound for the serial number is (I believe they're printed sequentially). To be fair the guy spent his whole career learning how to count things!

CurtMonash3• 11 years ago

Yes. Anything else would have been ... problematic.

simoncarter• 11 years ago

Before clicking on the link, I thought for some reason this would be article explaining how Paul Graham had got his own number, much like the Erdos number http://en.wikipedia.org/wiki/Paul_Erd%C5%91s#Erd.C5.91s_numb....

nevdka• 11 years ago

How many steps removed are you from starting a company with Paul Graham...

ikeboy• 11 years ago

I read hacker news, so 1?

ctdonath• 11 years ago

Here's an excellent and brain melting expose of Graham's Number: http://waitbutwhy.com/2014/11/1000000-grahams-number.html

shurcooL• 11 years ago

Thanks for finding it and linking. That has got to be one of the most entertaining (and educational) math articles that anyone can read/understand.

Some of my favorite parts (minor spoilers):

Look closely at that drawing until you realize how not okay it is. Then let’s continue.
Then Graham decides that for g2, he’ll just do the same thing as he did in g1, except instead of four arrows, there would be NO I CAN’T EVEN arrows.

torthrw• 11 years ago

Nothing really trumps this article on big numbers. http://www.scottaaronson.com/writings/bignumbers.html

noobermin• 11 years ago

"[T]he observable universe is far too small to contain an ordinary digital representation of Graham's number, assuming that each digit occupies one Planck volume."

Sheesh.

markrages• 11 years ago

Mentioned in xkcd: http://xkcd.com/207/

thret• 11 years ago

Now I'm horrified too.

foklepoint• 11 years ago

Graham is the coolest UCSD professor I have ever had a conversation with. I remember a particular instance, at the beginning of my first quarter at UCSD. I wasn't familiar with his work and had never heard of him. My naive 19 year old self walked into his office hours asking some simple probability question. I noticed a cast on his hand and inquired about it. He jokingly said he got a cut because he was juggling ice skates. I thought he was joking. I went home and looked him up, only to find that he was the head of the national jugglers association at one point. Pretty awesome guy.

to3m• 11 years ago

Interesting that they feel the need to specify which problem this number is an upper bound for...

excalq• 11 years ago

Related to that is Tetration, which can be expressed with complex numbers resulting in some beautiful fractal graphs: https://en.wikipedia.org/wiki/Tetration#Extensions

a3_nm• 11 years ago

There was a contest to write the 512-char C program that generated the largest number (but still terminates), assuming that all integer types are unbounded: http://djm.cc/bignum-results.txt

The method used by the winning entry is extremely interesting: return the outputs of all possible programs up to a certain size which terminate according to the calculus of constructions. It's quite crazy to have done this in 512 chars.

Ronsenshi• 11 years ago

I love this video http://www.youtube.com/watch?v=1N6cOC2P8fQ by Sean Day[9] Plott describing Graham's number very well. At least I found that description very easy to follow. Numberphile [1] too has a great explanation, but I still strongly recommend watching Day[9] video because it tells a little bit of history and Sean is very expressive and good speaker so he easily engages viewer.

[1] https://www.youtube.com/watch?v=XTeJ64KD5cg

leni536• 11 years ago

I think fast growing functions could be interesting as well. My favorite example is the "busy beaver function"[1]. It has been shown that it grows faster asymptotically than any computable function, where computability roughly means that you can write an algorithm to calculate its value (without memory or running time constrains).

Note that the Graham number can be written as G=f[64](4), where [.] means the number of iterations of f and f(4)=3\up\up\up\up3 (as in the article). Now you can define a function g(n) as g(n):=f[n](4), so G=g(64). g is computable since we just described an algorithm to calculates its values. So the busy beaver grows even faster (asymptotically) than g.

[1] http://en.wikipedia.org/wiki/Busy_beaver

Graham's Number

Related Stories