If I call the Ackermann Function with Graham's number as both of its arguments will it be less than $g_{65}$

In xkcd comic 207 it states that

[xkcd] means calling the Ackermann function with Graham's number as the arguments just to horrify mathematicians.

$A(g_{64},g_{64})$

In this explanation it states that

Even simply making $g_{65}$ dwarfs the number $A( A(g_{64}, g_{64}), A(g_{64}, g_{64}))$ into insignificance.

So:

Is $g_{65}$ greater than $A(g_{64}, g_{64})$?

And is it greater than $A( A(g_{64}, g_{64}), A(g_{64}, g_{64}))$?

• What is the question? Jun 13, 2014 at 10:40
• Am I to understand that you are surprised that Graham's number is not the largest number?
– 5xum
Jun 13, 2014 at 10:43
• Sorry just noticed there was no actual question, and put it in. Jun 13, 2014 at 10:46

I never understood how any of this should horrify mathematicians. After all, numbers are numbers and the Grahams number and the Ackermann function are closely related anyway. We have, using up arrow notation

$$A(m,n) = 2\uparrow^{m-2} (n+3) - 3$$

and

$$g_n = 3 \uparrow^{g_{n-1}} 3$$

So $A(g_{64},g_{64}) = 2 \uparrow^{g_{64}-2} (g_{64}+3) - 3$

which seems to me to be rougly about the same order of absurdly hugeness. In fact using the inequality from the answer to this, we get

$$A(g_{64}+2,1) + 3 = 2 \uparrow^{g_{64}} 4 < 3 \uparrow^{g_{64}} 3 = g_{65} < 2 \uparrow^{g_{64}} 5 - 2 = A(g_{64}+2,2) -2$$

But then using the recursive definition of the Ackermann function we get the lower bound

$$g_{65} > A(g_{64}+2,1) + 3 = A(g_{64}+1,A(g_{64}+2,0)) + 3 = A(g_{64}+1,g_{64}+3) +3 > A(g_{64},g_{64})$$

but only slightly, concerning the size of those constants $+1$ and $+3$ compared to $g_{64}$. So on the other hand $A(g_{64}+2,2) - 2$ is way smaller than $A(A(g_{64},g_{64}),A(g_{64},g_{64}))$, which is the answer to your second question.

• So is $A( A(g_{64}, g_{64}), A(g_{64}, g_{64}))$ greater or less than $g_{65}$ Jun 13, 2014 at 13:16
• It is greater, since $A(A(g_{64},g_{64}),A(g_{64},g_{64})) > A(g_{64}+2,2)-2 > g_{65}$. In fact by the same argument, $A(A(g_{64},g_{64}),A(g_{64},g_{64}))$ already nearly is $g_{66}$.
– mlk
Jun 13, 2014 at 13:32