Large numbers

Posted on by

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))))))

156 thoughts on “Large numbers”

  1. I think you meant:

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

    H is an operator that takes a function and returns a function.
    BB(9) is a number , not a function.
    Therefore H cannot be applied to BB(9).

  2. Why is it not computable? It might take a while to figure out BB(9), but we have that time. And we all know that x^n is computable, don’t we?

  5. Why is it not computable? It might take a while to figure out BB(9), but we have that time.

    The BB function isn’t computable, since if there was an algorithm to compute the value of BB(n), then we’d be able to place an upper bound on the length of halting computations for Turing machines of size n, which would provide a solution to the halting problem. Since the halting problem has no solution, this means that BB(n) is not computable.

    The value that the BB function maps 9 to is, of course, a finite number, and thus can be computed (i.e. there exists a TM that can output said number to arbitrary precision, independent of it being the output of the BB function), but I don’t think that’s the question you were really asking.

  6. Busy Beaver grows faster than any computable function in the “big O” sense. This means that for any computable function f, there exists an x0 and an M such that BB(x) > Mf(x) for all x>=x0. If this were not true, if there existed an f, x0, and M such that BB(x) =x0, you could use f in place of BB to solve the halting problem. The question is, what value of x0 do you use to show that the Ackerman function is O(BB)?

  7. To Johnicholas:

    I think H is not a function, it’s more like a macro that matches F(expression).

    So you can’t ask H(4), but you can make square(x) = x*x and ask H(square(4)):

    H(square(4)) = square^4(4) = (((4^2)^2)^2)^2 = 2^32

    Maybe this is the intended way:
    H(F(n)) = F^{n}(n) # changing notation so that i’ll be clearer, forget char counting :-)

    X1 = H(H(H(H(BB(9))))) = F(n) => F = H, n = H(H(H(BB(9))))
    so
    X1 = H^{H(H(H(BB(9))))}(H(H(H(BB(9)))))

    X2 = H(H(H(BB(9)))) = F(n) => F = H, n = H(H(BB(9)))
    so
    X2 = H^{H(H(BB(9)))}(H(H(BB(9))))

    and

    X1 = H^{H^{H(H(BB(9)))}(H(H(BB(9))))}(H^{H(H(BB(9)))}(H(H(BB(9)))))

    and so on…

  8. All of this big-number talk reminds me of a Metamagical Themas column:

    Douglass Hofstadter ran a contest in Scientific American called the Luring Lottery. He asked that people request as many or as few entries as they liked by sending him a single postcard with the number, or a way to find the number, written on it. The winner would recieve ($1,000,000 / entries) where entries is the total number of entries he received.

    He got postcards packed with recursive factorials, postcards packed with nines, and postcards covered in function definitions that avoided clear patterns but created even larger numbers than any of the others. The prize was close enough to zero that it wasn’t a problem that he couldn’t compute the number of entries.

  9. Largest number in 32 characters? Pfft. I can do it in one:

    x

    How’s that for elegant? Or, I suppose a more rigorous definition in 18 characters could be:

    lim(x->infinity) x

    Cheating… I know, I know.

  17. Did I get something wrong?

    H{H{H{H{BB(9)}}}} = H{H{H{(BB^9)(9)}}} = H{H{((BB^9)^9)(9)}} = H{(((BB^9)^9)^9)(9)} = ((((BB^9)^9)^9)^9)(9)

    Not that much, at least with a wimpy slow-growing function like Ackermanns instead of BB ;)

    I’d just cheat and borrow Conway’s arrows:
    Z(a)=a->…->a (a times);Z^9(9)

    (It’s easy to note that this is hell of a lot more than g64, A(g64,g64) or even *gasp* g65..)

  18. lim_n->inf aleph_n ? the infinity of infinities? computability is one thing, the size of “numbers” your are even able to express at all is another (e.g. N vs. R )

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

    Its a slight variation, using F(n) as the number of iterations per recursion(or is it recursion per iteration?) leaving us room for one less nesting. i’m not sure if it is actually bigger, but to me it feels bigger… plus the algebra hurts more.

  20. It is quite confusing. Considering 216 and Wendel’s comments… I originally thought 216 is wrong.

    If H is a normal transform (function to function), in the mathematical sense, I believe 216 is actually correct.

    Take f(n) = n^2

    H{f(2)} (or H{f}(2), rather?) is f^2(2), or f(f(2)), which is (2*2)*(2*2), i.e. 16.

    The transformed function H{f}(n) becomes f^n(n); we get a new function g(n). If evaluated at 2, we get the function g(n) = (n^4) with n=2. Now H{H{f(n)}} or H{H{f}}(n) becomes H{g(n)} at n=2, or g^2(2).

    However, “clearly” (?) what was meant by the author was that the second H{} transformation in H{H{f(2)}}, should have the effect of ^16, i.e. that it should be as Wendel explains. I.e. what was meant (?) was that H{f(2)} was supposed to return 16, but maintain the “f” as is. I.e. that H{H{f(2)}} should become H{f(16)} and thus be f^16(16).

    That makes the notation rather non-standard, in a mathematical sense? The xkcd author (sorry, don’t know his (her?;) name) seems to be more into computer science / programming than into maths?

  24. Jacob Haller, that number does not exist:
    Lets say it existed, and call it x.
    If define y = ‘the largest number definable in 49 characters’, I just defined y in 45 characters, so y

  26. Could you not also square it to get an even biger number with one more character?

    I have no basis in math for this, I had to count the fingers on my hand to work out the number for the spam protection, and I got it wrong the first time!

  27. a←b=a→…→a
    b a’s
    a↓b=a←…←a
    b a’s
    9↓9

    I guess it depends what you count as characters and what you count as formatting.

  28. At the risk of being pedantic, your definition is not well-posed — F(n) is just a number (element of the codomain of F), and there is no way to pull F and n back out of that number to use the way you are doing. For example, H(square(4))=H(16) should be the same as H(f(16)) where f is constant with value 16.

    So you would need to write H(F,n)=F(n)^n or use the haskell-like form
    H F n = …
    which actually saves some characters.

  31. Well, this would be larger:

    G(n)=BB^(G(n-1))(n);G(0)=9^9^9!;G(9!)

    but none of these seem to be particularly elegant. At least not as elegant as 1+e^(Ï€i)=0

  32. If we trade in largeness for elegance, we can use: BB(# bytes served by xkcd.com)
    However, this is a function of time, not a constant.

  33. Perhaps the challenge should require that you not repeat any operators, functions, or numbers, and that you cannot define new functions. Then it becomes more of a challenge to find the optimal ordering of the fastest growing operators/functions.

    for example:

    BB^(A(g64,3↑(5)7))(8->9!)*2+1/0

  34. But if we’re going for elegance we want as few operators as possible, to make it more intuitive:
    BB_g64(g64)

  35. Ok, it’s a bit unclear what “standard notation” means but to save some characters I will use prefix notation. Just like the original author I use ^ as the operator transforming a function f into it aplied to itself n times. In prefix notation it will have the syntax ^nf.

    f=BB;^^^^^^^^^!9f9f9f9f9f9f9f9f9

  36. Given an infinite flat plane with a certain initial population density and growth function of humans, if we place a male and female velociraptor on this plane at time t=0, the population growth of the velociraptors is known as the VV, or vicious velociraptor function.

    my number will be VV(65 million years) for an initial population density equal to that of Mexico City and a growth function of e^t

  37. This is 32 characters long; and it seems like it’s bigger than the new xkcd number, but I’m really really uncertain. It works by defining a new entity, ~, with a function on its left and a number on its right.

    F~n=F^F~(n-1)(n);F~0=99!;BB~BB~9

    The idea is to recurse the repeated composition part.

    Ugh. My head now hurts.

  38. In the same notation as above but inspired by Alex:

    fn=^f-n1Bn;gn=^g-n1fn;f0=g0=9;g9

    (Ok, I had to skip one B in BB to make it fit.)

  40. I think I have to suggest this:
    g_9999999999999999999999999999
    Thirty characters, the 9999999999999999999999999999th number in Graham’s series.

    It might not be elegant, but it satisfies the 30-character requirement, and it’s pretty mind-bogglingly huge.

  41. I’m having a lot of trouble with this, not least of which because, as others have noted before, Randall’s notation is total crap.

    Johnicholas Hines had a good idea on correcting the central problem, but he made a typo. What he meant was:

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

    This is actually much harder to analyze than it looks like, because notice that you can’t just replace H{F} with F^n — you don’t actually *know* n until it’s passed in with an argument.

    Since my ~ operator idea makes much more sense than this, I’m compelled to believe that it does not do the same thing as the original, and consequently, to admit that my earlier form is probably bested by the Hines xkcd Number.

  42. Chris Drost: I’m still confused about your notation. The only interpretation of:

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

    that makes any sense to me is to interpret H sort of like a makro in C. But that would give:

    H{ H { H { H{BB} } } } (9)=(((BB^9)^9)^9)^9(9)=BB^(9^4)(9)=BB^6561(9)

    Is that the correct interpretation?

  43. # Ed Says:
    But if we’re going for elegance we want as few operators as possible, to make it more intuitive:

    If there’s one thing I’ve learned from computer programming, it’s that elegance is in direct opposition of intuition.

  44. John: Not quite. You’re still thinking of the 9′s as if they were inside the curly brackets; they’re not.

    Okay, so let me try to explain this.

    First, to make this all simpler, lets use the number 4 where Randall Munroe used 9. That will make the number of brackets much more manageable.

    Consider just H{BB}(4) . What does that mean? That means:

    H{BB}(4) = BB^4(4) = BB( BB( BB( BB( 4 ) ) ) )

    Grand, no problem, everything looks good.

    Well, notice that H{BB}(n) is actually defined for all whole number n. I mean, we have:

    H{BB}(1) = BB(1) = 1
    H{BB}(2) = BB(BB(2)) = BB(4) = 13
    H{BB}(3) = BB(BB(BB(3))) = BB(BB(6)) = something.

    So, H{BB}(n) is actually a function in its own right. Let’s call it the busy-busy beaver function, and denote it with BBB(n).

    And since BBB is a function, we can now call H on it. What does H {BBB} (4) look like?

    H { H{BB} } (4) = H {BBB} (4) = BBB^4(4)

    H { H{BB} } (4) = BBB( BBB( BBB( BBB(4) ) ) )

    Now, see, H { H{BB} } = H { BBB } is yet another function. We might call it the Super Busy Beaver, denote it by SBB(n). And it’s defined well for n=1,2,3,… So we can apply H to *that*.

    That’s what this string of curly brackets means.

    Does that make sense, now?

  45. 216′s function could be tightened up more for a higher number

    “Z(a)=a→…→a (Z(a-1) times);Z^9(9)”

    of course, it all depends on whether Unicode counts.

  46. Would

    H{F}(n) = F^n(n); H{ H { H { H{BB} } } } (9)
    be the same thing as

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

    in which case

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

    would be larger (and shorter, you could throw a few factorials in there if you want). Or is that notation not widely used? Would it be ambiguous?

    Does H^2{BB}(9) mean:
    H{ H{ BB } } (9) or
    H{ BB }( H{ BB } (9) )

    Is there any way to apply the H function to itself in this way?

  47. #Is there any way to apply the H function to itself in this way?

    Actually, I think that’s what Russell was going for in his original equation. If you look at

    H{ F(n) } = F^n(n)

    and if you define H^m{ F(n) } = H{ H {… F(n)…} (m nestings of H{…})

    it would result in some collossally large function to say the least, which I assume he was intending (I could be wrong). However, I don’t think the F^n() notation is compatible with a meta-fuction (or whatever their name is) like H{}.

    For example,
    if
    H{ F(n) } = F^n(n) (original equation)
    and
    H^m{ F(n) } = H{ H {… F(n)…} (m nestings)
    then
    H{ H{ F(n) } } = H^F(n){ F(n) }
    and reducing the LHS to our H^m{} notation
    H^2{ F(n) } = H^F(n){ F(n) }
    yields
    2 = F(n)

    So, unless all functions, for all values of n, are equal to 2, there is a problem with the H^2{} notation.

  49. # So, unless all functions, for all values of n, are equal to 2, there is a problem with the H^2{} notation.

    It’s not a problem with the H^2 notation; it’s a problem with Randall’s notation.

    You’re treating H a lot like Randall treated it — as if it were some sort of function. Notice that H{ F(n) } is a little messed up, because F(n) is a single number — not a function plus an argument. It doesn’t include the separation between F and n.

    As such, Munroe’s second xkcd Number (MxN2) doesn’t actually make a whole lot of sense. But Hines’s xkcd Number (HxN), does.

    Here’s a 32-character version of the Hines xkcd number in operator notation, defining an operator Ω:

    U=ΩF iff U(n)=F^n(n);(ΩΩΩΩ BB)(9)

    Exponents work just fine with Ω. The thing on the left could be simplified by (Ω^4 BB)(9).

  50. BB(n) is not computable, OK. But with some luck there are no TMs with size 9 where the halting problem _for these TMs_ is undecidable. In fact it is unknown if BB(5) can be computed (although being a very large number), but for for BB(4) someone managed to find a solution by trying out all TMs (and proving non-termination of some). I don’t really think that saying “BB(9) is decidable” is correct, but it might be. For arbritrary n it is, for sure.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>