Graham's Number

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."

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

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

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

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.

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.

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....

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

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

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

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

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

"[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.