"[xkcd] means calling the Ackermann function with Graham's number as the arguments just to horrify mathematicians."
The Ackermann function is defined as follows: A(m,n) = n+1 if m=0, A(m-1, 1) if m>0 and n=0, A(m-1, A(m,n-1)) if m>0 and n>0.
A(0,n) = n+1, which is obvious.
A(1,n) = A(0, A(1, n-1)) = A(1, n-1) + 1. Thus we have A(1,n) = n+k for some constant k. Now, A(1,0) = A(0,1) = 2, we have A(1,n) = n+2.
The same sort of reasoning leads to A(2,n) = 2n+3, A(3,n) = 2n+3 - 3.
A(4,n) can be written down it's 2^(2^(2^(2^...2)))...) - 3, where there are n+3 twos. (Incidentally, power towers should be evaluated from the right to the left; p^q^r is p^(q^r), not (p^q)^r. The reason I say this is because it's clear we should be consistent and either evaluate from left to right or from right to left, and there's already a perfectly good way of writing (p^q)^r, namely p^(qr).)
But A(5,n) and A(6,n) can't be written nicely.
And Graham's number, denoted g64, is already obscenely large; I'm not going to bother writing out how to define it, you can read Wikipedia. It's an upper bound for the answer to the following problem:
Consider an n-dimensional hypercube, and connect each pair of vertices to obtain a complete graph on 2n vertices. Then colour each of the edges of this graph using only the colours red and black. What is the smallest value of n for which every possible such colouring must necessarily contain a single-coloured complete sub-graph with 4 vertices that lies in a plane?
and the correct answer to this problem was suspected, for a long time, to be 6.
The author of xkcd claims that A(g64, g64) is probably the largest number ever concisely defined. Of course, one can always define a larger number. I nominate gk, where k = A(g64, g64); this number has the unfortunate property that it requires double-subscripts to write. In my opinion, good mathematical notation avoids double subscripts when at all possible.
Of course, this is all just a more mathematically sophisticated version of the "infinity plus one" that makes an appearance every so often on playgrounds. There's always a bigger number. (Although, if you want to get technical, all the numbers I mentioned are finite!)
And the xkcd number A(g64, g64) is only "concisely defined" if you've defined Graham's number and the Ackermann function, which themselves take some work. So what's the largest number you can write with, say, four characters, chosen from some "reasonable" set of characters in our standard mathematical notation? The two obvious candidates are A = 9^(9^(9^9))) or B = 9!!!. (Note that the first of these can be written in four characters if properly formatted.) In fact, A>B. We can see this by taking the logarithm of each of them twice
log A = 9^(9^9) log 9
log log A = log 9^(9^9) + log log 9
log log A = 9^9 log 9 + log log 9 = 851249821
Now, to take the log of a factorial, we recall Stirling's approximation, which I've used before. We have the approximate equality
log n! ~ 1/2 log (2π) - n + (n+1/2) log n
for our purposes we can use the much cruder approximation log n! < 2n log n. Then we have
log B < 2(9!!) log 9!!
log log B < log 2 + log(9!!) + log log (9!!)
log log B < log 2 + 2(9! log 9!) + log ( 2(9! log 9!) ) = 9291071.
Finally, all this business reminds me of a talk I went to about large numbers. Every time the speaker was about to prove that one ridiculously large number was larger than another, the fire alarm went off. It seemed as if the building didn't want us to talk about such large numbers that day, as if we were going to give away the secret of the universe.
3 comments:
Actually, Randall addressed the "concise" misgiving in this blag post, and the subsequent discussion carried for quite a ways.
The xkcd number thing always felt really unsatisfactory to me, mainly because the Ackermann function is so incredibly asymmetric in its growth rate. I haven't tried doing the explicit computation, but I would guess that A(g_64,g_64) < A((g_64)+1,5). (I'm a bit more confident in guessing that there is an absolute constant N so that A(m,m) < A(m+1,N) for any m. Again, I ought to work this out. Maybe that would be a good thing to do in the two weeks of boredom/pretending to study for my qual I have left before starting graduate school.)
But I'm not sure how to modify the xkcd number so as not to have this sort of ``flaw.'' There is a paper by Joel Spencer in the American Math Monthly (maybe around 1980) that discusses interesting strategies for winning the large number game assuming you aren't competing against logicians or other people who have read the paper.
ComplexZeta,
You are correct, A(g_64+1,5) > A(g_64,g_64). Though, 2 1/2 years later you have likely either figured this out yourself or stopped caring, but for anyone reading this thread, the number 'N' that you are looking for is 1, thus:
A(g_64+1,5) > A(g_64+1,1) > A(g_64,g_64)
Definition of the Ackermann function:
A(m,n) = n+1 if m = 0
A(m,n) = A(m-1,1) if m > 0, n = 0
A(m,n) = A(m-1, A(m,n-1)) if m > 0, n > 0
Therefore:
A(m+1,1) = A(m, A(m+1,0)) = A(m,A(m,1)) > A(m,m) iff A(m,1) > m for all m, which it is.
Incidentally, the special case of A(m,n) where m = n, is often expressed as a unary version of the Ackermann function: A(n), so xkcd could have simply expressed the xkcd number as A(g_64), which would have meant the same thing, but the unary version of the Ackermann function is less well known, so I think xkcd used the more commonly understood, but slightly less elegant expression A(g_64, g_64).
The unary Ackermann function can also be called on itself and often is:
A(A(n)) which can be expressed as A^2(n). Note that this is not the same as A(n^2). More generally:
A^m(n) = A(A^(m-1)) for m > 1
A^m(n) = A(n) for m = 1
Using this notation, Graham's number is approximately equal to A^64(4), which makes the xkcd number approximately equal to A(A^64(4)) = A^65(4).
Note that this is still far, far smaller than TREE(3).
Post a Comment