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

Question

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}))$?

Answer 1

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.