User lexivore - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T15:24:32Z http://mathoverflow.net/feeds/user/4130 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11934/magnitude-of-grahams-number/15946#15946 Answer by Lexivore for Magnitude of Graham's Number? Lexivore 2010-02-21T00:39:29Z 2010-02-21T00:45:16Z <p>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&uarr;<sup>(m-2)</sup>(n+3)-3. So the first step of the Graham's function, 3&uarr;&uarr;&uarr;&uarr;3 = g<sub>1</sub>, is very roughly A(6,6). The second step g<sub>2</sub> is roughly A(g<sub>1</sub>,g<sub>1</sub>) and the actual Graham's number, g<sub>64</sub>, is roughly A(g<sub>63</sub>,g<sub>63</sub>). That's how big Graham's number is.</p> <p>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 A<sup>64</sup>(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 A<sup>A(187196)</sup>(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. </p> <p>TREE(3) is so much bigger then those numbers that it hurts my brain to think about it. So I won't.</p>