Large numbers

I mentioned an extremely large number in this comic, and then talked a little about comparing it to another large number in this blag post. But all the numbers discussed had a sense of arbitrariness to them. The xkcd number was just a function that grew rapidly plus a large argument. I’ve been thinking about it, and I want to construct a number that is not only mind-bogglingly large, but elegantly large. This is hard to define — the closest I can get is that it shouldn’t feel arbitrary.

Now, as some have pointed out, noncomputable functions like the Busy Beaver function can grow faster than any computable function. By my understanding, this just means they have a higher computational complexity — their values for a little bit may be smaller than a computable function, but you can never prove that, for sufficiently large arguments, a computable function is an upper bound to the sequence.

I decided I wanted to express the largest number I could in about 32 characters, something akin to the MIT big number duel. Here’s what I came up with:

H{F(n)}=F^n(n);H{H{H{H{BB(9)}}}}

In the first half (before the semicolon) I’m defining an operator H, which transforms a function F and an argument n into an n-level recursive call to itself (I’m using F^n() to refer to F(F(F( … recursed n times … ))) as in derivatives. That is, H{} represents the process of n-level recursion. Then I use this recursion several times on the Busy Beaver function until I run out of space. This isn’t just four recursions — each new H{} is a virtually infinite set of recursions, since it has as many levels as the result of the number in the level below it. As the seed, I picked 9 — the largest integer you can fit in a single digit.

I’m a lot happier with this number’s ‘bigness’ than I was with A(g_64, g_64). It feels bigger, in some hard-to-describe way (it also feels bigger in the easy-to-describe way: “>”). It uses a more fundamental idea of bigness It’s also, of course, noncomputable. However, you can stick the Ackermann function in place of the Busy Beaver function and get a number that is again much larger than the xkcd number.

So, anyone want to define an elegantly bigger number in about 32 characters, invoking reasonably standard notation and functions? I’m sure it’s possible — it’s not a well-defined contest, and I’m sure there are a lot of other tricks you can use. But at least I’m finally satisfied with my entry.

Edit: As a number of commenters have pointed out, my notation here is pretty bad.Â  I’m indeed using H{} more like a macro that acts on an expression than a transform that acts on a function, and this leads to difficulties in mixing the levels.Â  Fortunately, you guys have waded through the fog and understood what I was getting at 🙂

Here’s a slightly simplified expression that does the same thing and tacks in two extra recursions (so as to use the 32 characters).Â  It loses the generality I was going for, but it’s more compact and not ambiguous:

H(n)=BB^n(n);H(H(H(H(H(H(9))))))