7
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What is the question? $\endgroup$ – Marcin Łoś Jun 13 '14 at 10:40
  • 1
    $\begingroup$ Am I to understand that you are surprised that Graham's number is not the largest number? $\endgroup$ – 5xum Jun 13 '14 at 10:43
  • $\begingroup$ Sorry just noticed there was no actual question, and put it in. $\endgroup$ – user288447 Jun 13 '14 at 10:46
11
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So is $A( A(g_{64}, g_{64}), A(g_{64}, g_{64}))$ greater or less than $g_{65}$ $\endgroup$ – user288447 Jun 13 '14 at 13:16
  • 2
    $\begingroup$ 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}$. $\endgroup$ – mlk Jun 13 '14 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.