MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 deleted 2 characters in body

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,1). 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.

1

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