Interesting that they feel the need to specify which problem this number is an upper bound for...
Graham's Number
21–27 of 27 posts
Re: Graham's Number
#22Related to that is Tetration, which can be expressed with complex numbers resulting in some beautiful fractal graphs: https://en.wikipedia.org/wiki/Tetration#Extensions
Re: Graham's Number
#23Re: Graham's Number
#24There 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.
Re: Graham's Number
#25I 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.
Re: Graham's Number
#26I 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.
Re: Graham's Number
#27Earlier quoted context omitted.
Yes. Anything else would have been ... problematic.
You should have told him "I expected you to say that" and let infinite recursion reign free. :)
No, that's something to do in a Hilary Putnam philosophy class. He's the one who announces at the beginning of the term there will be a two-part final:
A. Write a question suitable for this course. B. Answer it. You will be graded on both parts.