89
$\begingroup$

Popular mathematics folklore provides some simple tools enabling us compactly to describe some truly enormous numbers. For example, the number $10^{100}$ is commonly known as a googol, and a googol plex is $10^{10^{100}}$. For any number $x$, we have the common vernacular:

  • $x$ bang is the factorial number $x!$
  • $x$ plex is the exponential number $10^x$
  • $x$ stack is the number obtained by iterated exponentiation (associated upwards) in a tower of height $x$, also denoted $10\uparrow\uparrow x$, $$10\uparrow\uparrow x = 10^{10^{10^{\cdot^{\cdot^{10}}}}}{\large\rbrace} x\text{ times}.$$

Thus, a googol bang is $(10^{100})!$, and a googol stack is $10\uparrow\uparrow 10^{100}$. The vocabulary enables us to name larger numbers with ease:

  • googol bang plex stack. (This is the exponential tower $10^{10^{\cdot^{\cdot^{^{10}}}}}$ of height $10^{(10^{100})!}$)
  • googol stack bang stack bang
  • googol bang bang stack plex stack
  • and so on…

Consider the collection of all numbers that can be named in this scheme, by a term starting with googol and having finitely many adjectival operands: bang, stack, plex, in any finite pattern, repetitions allowed. (For the purposes of this question, let us limit ourselves to these three operations and please accept the base 10 presumption of the stack and plex terminology simply as an artifact of its origin in popular mathematics.)

My goal is to sort all such numbers nameable in this vocabulary by size.

A few simple observations get us started. Once $x$ is large enough (about 20), then the factors of $x!$ above $10$ compensate for the few below $10$, and so we see that $10^x\lt x!$, or in other words, $x$ plex is less than $x$ bang. Similarly, $10^{10^{:^{10}}}x$ times is much larger than $x!$, since $10^y\gt (y+1)y$ for large $y$, and so for large values we have

  • $x$ plex $\lt$ $x$ bang $\lt$ $x$ stack.

In particular, the order for names having at most one adjective is:

 googol  googol plex  googol bang  googol stack 

And more generally, replacing plex with bang or bang with stack in any of our names results in a strictly (and much) larger number.

Continuing, since $x$ stack plex $= (x+1)$ stack, it follows that

  • $x$ stack plex $\lt x$ plex stack.

Similarly, for large values,

  • $x$ plex bang $\lt x$ bang plex,

because $(10^x)!\lt (10^x)^{10^x}=10^{x10^x}\lt 10^{x!}$. Also,

  • $x$ stack bang $\lt x$ plex stack $\lt x$ bang stack,

because $(10\uparrow\uparrow x)!\lt (10\uparrow\uparrow x)^{10\uparrow\uparrow x}\lt 10\uparrow\uparrow 2x\lt 10\uparrow\uparrow 10^x\lt 10\uparrow\uparrow x!$. It also appears to be true for large values that

  • $x$ bang bang $\lt x$ stack.

Indeed, one may subsume many more iterations of plex and bang into a single stack. Note also for large values that

  • $x$ bang $\lt x$ plex plex

since $x!\lt x^x$, and this is seen to be less than $10^{10^x}$ by taking logarithms.

The observations above enable us to form the following order of all names using at most two adjectives.

 googol  googol plex  googol bang  googol plex plex  googol plex bang  googol bang plex  googol bang bang  googol stack  googol stack plex  googol stack bang  googol plex stack  googol bang stack  googol stack stack 

My request is for any or all of the following:

  1. Expand the list above to include numbers named using more than two adjectives. (This will not be an end-extension of the current list, since googol plex plex plex and googol bang bang bang will still appear before googol stack.) If people post partial progress, we can assemble them into a master list later.

  2. Provide general comparison criteria that will assist such an on-going effort.

  3. Provide a complete comparison algorithm that works for any two expressions having the same number of adjectives.

  4. Provide a complete comparison algorithm that compares any two expressions.

Of course, there is in principle a computable comparison procedure, since we may program a Turing machine to actually compute the two values and compare their size. What is desired, however, is a simple, feasible algorithm. For example, it would seem that we could hope for an algorithm that would compare any two names in polynomial time of the length of the names.

  • 5
    Just to get it out of the way: have you seen [this](http://www.jstor.org/pss/27642031)?2011-10-14
  • 2
    If you are intending to agree with Knuth's uparrow notation, then $10 \uparrow x$ is just $10^x$, while $10 \uparrow \uparrow x$ is an exponent tower of $10$'s having height $x$.2011-10-14
  • 0
    @JDH: Some of the computations in the references I posted at http://mathoverflow.net/questions/11934 may be of interest to you.2011-10-14
  • 0
    Thanks for the links! Austin, I have corrected.2011-10-14
  • 44
    I declare this question "**The Ultrafinitists Nightmare!**" :-)2011-10-15
  • 1
    which is the first out of (google,google bang, google bang bang, ...) to be larger than a google stack?2011-10-16
  • 0
    @QED, it seems we can iterate bang an enormous number of times, but I'm not sure how many.2011-10-16
  • 0
    Given that it is very difficult to understand how plex bang and stack interact together, I guess that you will not be able to use the same method forever, at some point the "for x big enough" will exceed a googol, but it's very hard to tell when. I would expect that there is no polynomial algorithm, and that every algorithm will have an incredibly huge complexity.2011-10-27
  • 2
    This is a fun problem!2011-10-27
  • 1
    @AsafKaragila Then you haven't seen anything yet ;)2017-03-06

2 Answers 2