Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
Just to get it out of the way: have you seen this? –  J. M. Oct 14 '11 at 17:27
1  
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$. –  Austin Mohr Oct 14 '11 at 18:07
    
@JDH: Some of the computations in the references I posted at mathoverflow.net/questions/11934 may be of interest to you. –  Dave L. Renfro Oct 14 '11 at 18:41
23  
I declare this question "The Ultrafinitists Nightmare!" :-) –  Asaf Karagila Oct 15 '11 at 13:47
1  
This is a fun problem! –  Grumpy Parsnip Oct 27 '11 at 1:08
show 4 more comments

2 Answers 2

OK, let's attempt a sorting of the names having at most three operands. I'll make several observations, and then use them to assemble the order section by section, beginning with the part below googol stack.

  • googol bang bang bang $\lt$ googol stack. It seems clear that we shall be able to iterated bangs many times before exceeding googol stack. Since googol bang bang bang is the largest three-operand name using only plex and bang, this means that all such names will interact only with each below googol stack.

  • plex $\lt$ bang. This was established in the question.

  • plex bang $\lt$ bang plex. This was established in the question, and it allows us to make many comparisons in terms involving only plex and bang, but not quite all of them.

  • googol bang bang $\lt$ googol plex plex plex. This is because $g!!\lt (g^g)^{g^g}=g^{gg^g}=10^{100\cdot gg^g}$, which is less than $10^{10^{10^g}}$, since $100\cdot gg^g=10^{102\cdot 10^{100}}\lt 10^{10^g}$. Since googol bang bang is the largest two-operand name using only plex and bang and googol plex plex plex is the smallest three-operand name, this means that the two-operand names using only plex and bang will all come before all the three-operand names.

  • googol plex bang bang $\lt$ googol bang plex plex. This is because $(10^g)!!\lt ((10^g)^{10^g})!=(10^{g10^g})!=(10^{10^{g+100}})!\lt (10^{10^{g+100}})^{10^{10^{g+100}}}=10^{10^{g+100}10^{10^{g+100}}}= 10^{10^{(g+100)10^{g+100}}}\lt 10^{10^{g!}}$.

Combining the previous observations leads to the following order of the three-operand names below googol stack:

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

Perhaps someone can generalize the methods into a general comparison algorithm for larger smallish terms using only plex and bang? This is related to the topic of the Velleman article linked to by J. M. in the comments.

Meanwhile, let us now turn to the interaction with stack. Using the observations of the two-operand case in the question, we may continue as follows:

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

Now we use the following fact:

  • stack bang bang $\lt$ plex stack. This is established as in the question, since $(10\uparrow\uparrow x)!!\lt (10\uparrow\uparrow x)^{10\uparrow\uparrow x}!\lt$ $(10\uparrow\uparrow x)^{(10\uparrow\uparrow x)(10\uparrow\uparrow x)^{10\uparrow\uparrow x}}=$ $(10\uparrow\uparrow x)^{(10\uparrow\uparrow x)^{1+10\uparrow\uparrow x}} 10\uparrow\uparrow 4x\lt 10\uparrow\uparrow 10^x$. In fact, it seems that we will be able to absorb many more iterated bangs after stack into plex stack.

The order therefore continues with:

  googol plex stack
  googol plex stack plex
  googol plex stack bang
  • plex stack bang $\lt$ bang stack. To see this, observe that $(10\uparrow\uparrow 10^x)!\lt (10\uparrow\uparrow 10^x)^{10\uparrow\uparrow 10^x}\lt 10\uparrow\uparrow 2\cdot10^x$, since associating upwards is greater, and this is less than $10\uparrow\uparrow x!$. Again, we will be able to absorb many operands after plex stack into bang stack.

The order therefore continues with:

  googol bang stack
  googol bang stack plex
  googol bang stack bang
  • bang stack bang $\lt$ plex plex stack. This is because $(10\uparrow\uparrow x!)!\lt (10\uparrow\uparrow x!)^{10\uparrow\uparrow x!}\lt 10\uparrow\uparrow 2x!\lt 10\uparrow 10^{10^x}$.

Thus, the order continues with:

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

This last item is clearly less than googol stack stack, and so, using all the pairwise operations we already know, we continue with:

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

Which seems to complete the list for three-operand names. If I have made any mistakes, please comment below.

Meanwhile, this answer is just partial progress, since we have the four-operand names, which will fit into the hierarchy, and I don't think the observations above are fully sufficient for the four-operand comparisons, although many of them will now be settled by these criteria. And of course, I am nowhere near a general comparison algorithm.

Sorry for the length of this answer. Please post comments if I've made any errors.

share|improve this answer
add comment

The following describes a comparison algorithm that will work for expressions where the number of terms is less than googol - 2.

First, consider the situation with only bangs and plexes. To compare two numbers, first count the total number of bangs and plexes in each. If one has more than the other, that number is bigger. If the two numbers have the same number of bangs and plexes, compare the terms lexicographically, setting bang > plex. So googol plex bang plex plex > googol plex plex bang bang, since the first terms are equal, and the second term favors the first.

To prove this, first note that x bang > x plex for $x \ge 25$. To show that the higher number of terms always wins, it suffices to show that googol plex$^{k+1} >$ googol bang$^k$. We will instead show that $x$ plex$^{k+1} > x$ bang $^k$ for $x \ge 100$. Set $x = 10^y$.

$10^y$ bang $< (10^y)^{10^y} = 10^{y*10^y} < 10^{10^{10^y}} = 10^y$ plex plex

$10^y$ bang bang $< (10^{y*10^y})^{10^{y*10^y}} $

$= 10^{10^{y*10^y + y + \log_{10} y}}$

$= 10^{10^{10^{y + \log_{10} y} (1 + \frac{y + \log_{10} y}{10^{y + \log_{10} y}})}}$

$< 10^{10^{10^{y + \log_{10} y} (1 + \frac{y}{10^{y}})}}$

(We use the fact that x/10^x is decreasing for large x.)

$= 10^{10^{10^{y + \log_{10} y + \log_{10}(1 + \frac{y}{10^{y}})}}}$

$< 10^{10^{10^{y + \log_{10} y + \frac{y}{10^{y}}}}}$

(We use the fact that ln(1+x) < x, so log_10 (1+x) < x)

$< 10^{10^{10^{2y}}} < 10^{10^{10^{10^y}}} = 10^y$ plex plex plex

$10^y$ bang bang bang < $(10^{10^{10^{y + \log_{10} y + \frac{y}{10^y}}}})^{10^{10^{10^{y + \log_{10} y + \frac{y}{10^y}}}}} $

$= 10^{10^{(10^{10^{y + \log_{10} y + \frac{y}{10^y}}} + 10^{y + \log_{10} y + \frac{y}{10^y}})}}$

$= 10^{10^{(10^{10^{y + \log_{10} y + \frac{y}{10^y}}}(1 + \frac{10^{y + \log_{10} y + \frac{y}{10^y}}}{10^{10^{y + \log_{10} y + \frac{y}{10^y}}}})}}$

$< 10^{10^{(10^{10^{y + \log_{10} y + \frac{y}{10^y}}}(1 + \frac{10^{y }}{10^{10^{y}}})}}$

$= 10^{10^{10^{(10^{y + \log_{10} y + \frac{y}{10^y}} + \log_{10}(1+\frac{10^{y }}{10^{10^{y}}}))}}}$

$< 10^{10^{10^{(10^{y + \log_{10} y + \frac{y}{10^y}} + \frac{10^{y }}{10^{10^{y}}})}}}$

$= 10^{10^{10^{(10^{y + \log_{10} y + \frac{y}{10^y}} (1 + \frac{10^{y }}{10^{10^{y}} * (10^{y + \log_{10} y + \frac{y}{10^y}})}))}}}$

$< 10^{10^{10^{(10^{y + \log_{10} y + \frac{y}{10^y}} (1 + \frac{1}{10^{10^{y}} }))}}}$

$= 10^{10^{10^{10^{y + \log_{10} y + \frac{y}{10^y} + \frac{1}{10^{10^{y}} }} }}}$

$< 10^{10^{10^{10^{2y}}}} < 10^{10^{10^{10^{10^y}}}} = 10^y$ plex plex plex plex

We can see that the third bang added less than $\frac{1}{10^{10^y}}$ to the top exponent. Similarly, adding a fourth bang will add less than $\frac{1}{10^{10^{10^y}}}$, adding a fifth bang will add less than $\frac{1}{10^{10^{10^{10^y}}}}$, and so on. It's clear that all the fractions will add up to less than 1, so in general,

$10^y$ bang$^{k} < 10^{10^{10^{\cdot^{\cdot^{10^{y + \log_{10} y + 1}}}}}}{\large\rbrace} k+1\text{ 10's} < 10^{10^{10^{\cdot^{\cdot^{10^{10^y}}}}}}{\large\rbrace} k+2\text{ 10's} = 10^y$ plex$^{k+1}$.

Next, we have to show that the lexicographic order works. We will show that it works for all $x \ge 100$. Suppose our procedure failed; take two numbers with the fewest number of terms for which it fails, e.g. $x s_1 ... s_n$ and $x t_1 ... t_n$. It cannot be that $s_1$ and $t_1$ are both plex or both bang, since then $(x s_1) s_2 ... s_n$ and $(x s_1) t_2 ... t_n$ would be a failure of the procedure with one fewer term. So set $s_1 =$ bang and $t_1 =$ plex. Since our procedure tells us that $x s_1 ... s_n$ > $x t_1 ... t_n$, and our procedure fails, it must be that $x s_1 ... s_n$ < $x t_1 ... t_n$. Then

$x$ bang plex ... plex $< x$ bang $s_2 ... s_n < x$ plex $t_2 ... t_n < x$ plex bang ... bang.

So to show our procedure works, it suffices to show that x bang plex$^k$ > x plex bang$^k$. Set x = 10^y.

$10^y$ bang > $(\frac{10^y}{e})^{10^y} > (10^{y - \frac{1}{2}})^{10^y} = 10^{(y-\frac{1}{2})10^y}$

$10^y$ bang plex$^k > 10^{10^{10^{\cdot^{\cdot^{10^{(y-\frac{1}{2})10^y}}}}}}{\large\rbrace} k+1\text{ 10's}$

To determine $10^y$ plex bang$^k$, we can use our previous inequality for $10^y$ bang$^k$ and set $x = 10^y$ plex $= 10^{10^y}$, i.e. substitute $10^y$ for $y$. We get

$10^y$ plex bang$^k < 10^{10^{10^{\cdot^{\cdot^{10^{(10^y + \log_{10}(10^y) + 1}}}}}}{\large\rbrace} k+1\text{ 10's} = 10^{10^{10^{\cdot^{\cdot^{10^{10^y + y + 1}}}}}}{\large\rbrace} k+1\text{ 10's}$

$< 10^{10^{10^{\cdot^{\cdot^{10^{(y-\frac{1}{2})10^y}}}}}}{\large\rbrace} k+1\text{ 10's} < 10^y$ bang plex$^k$.

Okay, now for terms with stack. Given two expressions, first compare the number of times stack appears; the number in which stack appears more often is the winner. If stack appears n times for both expressions, then in each expression consider the n+1 groups of plexes and bangs separated by the n stacks. Compare the n+1 groups lexicographically, using the ordering we defined above for plexes and bangs. Whichever expression is greater denotes the larger number.

Now, this procedure clearly does not work all the time, since a googol followed be a googol-2 plexes is greater than googol stack. However, I believe that if the number of terms in the expressions are less than googol-2, then the procedure is correct.

First, observe that $x$ plex stack > $x$ stack plex and $x$ bang stack > $x$ stack bang, since

$x$ stack plex $< x$ stack bang $< (10\uparrow\uparrow x)^{10\uparrow\uparrow x} < 10\uparrow\uparrow (2x) < x$ plex stack $< x$ bang stack.

Thus if googol $s_1 ... s_n$ is some expression with fewer stacks than googol $t_1 ... t_m$, we can move all the plexes and bangs in $s_1 ... s_n$ to the beginning. Let $s_1 ... s_i$ and $t_1 ... t_j$ be the initial bangs and plexes before the first stack. There will be less than googol-2 bangs and plexes, and

googol bang$^{\text{googol}-3} < 10^{10^{10^{\cdot^{\cdot^{10^{100 + \log_{10} 100 + 1}}}}}}{\large\rbrace} \text{googol-2 10's} < 10^{10^{10^{\cdot^{\cdot^{10^{103}}}}}}{\large\rbrace} \text{googol-2 10's}$

$ < 10 \uparrow\uparrow $googol = googol stack

and so googol $s_1 ... s_i$ will be less than googol $t_1 ... t_{j+1}$ ($t_{j+1}$ is a stack). $s_{i+1} ... s_n$ consists of $k$ stacks, and $t_{j+2} ... t_m$ consists of at least $k$ stacks and possibly some plexes and bangs. Thus googol $s_1 ... s_n$ will be less than googol $t_1 ... t_m$.

Now consider $x S_1$ stack $S_2$ stack ... stack $S_n$ versus $x T_1$ stack $T_2$ stack ... stack $T_n$, where the $S_i$ and $T_i$ are sequences of plexes and bangs. Without loss of generality, we can assume that $S_1 > T_1$ in our order. (If $S_1 = T_1$, we can consider ($x S_1$ stack) $S_2$ stack ... stack $S_n$ versus ($x T_1$ stack) $T_2$ stack ... stack $T_n$, and compare $S_2$ versus $T_2$, etc., until we get to an $S_i$ and $T_i$ that are different.) $x S_1$ stack $S_2$ stack ... stack $S_n$ is, at the minimum, $x S_1$ stack ... stack, while $x T_1$ stack $T_2$ stack ... stack $T_n$, is, at the maximum, $x T_1$ stack bang$^{\text{googol}-3}$ stack .... stack. So it is enough to show

x S_1 stack > x T_1 stack bang$^{\text{googol}-3}$

We have seen that $x$ bang$^k < 10^{10^{10^{\cdot^{\cdot^{10^x}}}}}{\large\rbrace} k+1\text{ times}$ so $x$ bang$^{\text{googol}-3} < 10^{10^{10^{\cdot^{\cdot^{10^x}}}}}{\large\rbrace} \text{googol-2 times}$, and $x T_1$ stack bang$^{\text{googol}-3} < ((x T_1) +$ googol) stack. Thus we must show $x S_1 > (x T_1) +$ googol.

We can assume without loss of generality that the first term of $S_1$ and the first term of $T_1$ are different. (Otherwise set $x = x s_1 ... s_{i-1}$ where i is the smallest number such that s_i and t_i are different.) We have seen above that it is enough to consider

x (plex)^(k+1) versus x (bang)^k x bang (plex)^k versus x plex (bang)^k

We have previously examined these two cases. In both cases, adding a googol to the smaller leads to the same inequality.

And with that, we are done.


What are the prospects for a general comparison algorithm, when the number of terms exceeds googol-3? The difficulty can be illustrated by considering the following two expressions:

$x$ $S_1$ stack plex$^k$

$x$ $T_1$ stack

The two expressions are equal precisely when k = $x$ $T_1$ - $x$ $S_1$. So a general comparison algorthm must allow for the calculation of arbitrary expressions, which perhaps makes our endeavor pointless.

In light of this, I believe the following general comparison algorithm is the best that can be done.

We already have a general comparison algorithm for expressions with no appearances of stack. If stack appears in both expressions, let them be $x$ $S_1$ stack $S_2$ and $x$ $T_1$ stack $T_2$, where $S_2$ and $T_2$ have no appearances of stack. Replace $x$ $S_1$ stack with plex$^{(x S_1)}$, and $x$ $T_1$ stack with plex$^{(x T_1)}$, and do our previous comparison algorithm on the two new expressions. This clearly works because $x$ $S_1$ stack = $10^{10}$ plex$^{(x S_1 -2)}$ and $x$ $T_1$ stack = $10^{10}$ plex$^{(x T_1-2)}$.

The remaining case is where one expression has stack and the other does not, i.e. googol $S_1$ stack $S_2$ versus googol $T$, where $S_2$ and $T$ have no appearances of stack. Let $s$ and $t$ be the number of terms in $S_2$ and $T$ respectively. Then googol $T$ is greater than googol $S_1$ stack $S_2$ iff $t \ge $ googol $S_1 + s - 2$.

Indeed, if $t \ge $ googol $S_1 + s - 2$,

googol $T \ge$ googol plex$^{\text{googol} S_1 + s - 2} = 10^{10^{10^{\cdot^{\cdot^{10^{100}}}}}}{\large\rbrace} $ googol $S_1$ $+s-1$ 10's $ > 10^{10^{10^{\cdot^{\cdot^{10^{10} + 10 + 1}}}}}{\large\rbrace} $ googol $S_1 +s-1$ 10's > googol $S_1$ stack bang$^s$

$\ge$ googol $S_1$ stack $S_2$.

If $t \le $ googol $S_1 + s - 3$,

googol $T \le$ googol bang$^{\text{googol} S_1 + s - 3} < 10^{10^{10^{\cdot^{\cdot^{10^{103}}}}}}{\large\rbrace} $ googol $S_1$ $+s-2$ 10's $ < 10^{10^{10^{\cdot^{\cdot^{10^{10^{10}}}}}}}{\large\rbrace} $ googol $S_1 +s$ 10's = googol $S_1$ stack plex$^s$

$\le$ googol $S_1$ stack $S_2$.

So the comparison algorithm, while not particularly clever, works.

In one of the comments, someone raised the question of a polynomial algorithm (presumably as a function of the maximum number of terms). We can implement one as follows. Let n be the maximum number of terms. We use the following lemma.

Lemma. For any two expressions googol $S$ and googol $T$, if googol $S$ > googol $T$, then googol $S$ > 2 googol $T$.

This lemma is not too hard to verify, but for reasons of space I will not do so here.

As before, we have a simple algorithm in O(n) time when both expressions do not contain stack. If exactly one of the expressions has a stack, we compute $x$ $S_1$ as above, but we stop if the calculation exceeds n. If the calculation finishes, then we can do the previous comparison in O(log n) time; if the calculation stops, then we know that $x$ $S_1$ stack $S_2$ is larger, again in O(log n) time.

If both expressions have stack, then from our previous precedure we calculate both $x$ $S_1$ and $x$ $T_1$. Now we stop if either calculation exceeds $2m$, where $m = $the maximum length of $S_2$ and $T_2$ (Clearly, $2m < 2n$). If the caculation finishes, then we can do our previous procedure in O(n) time. If the calculation stops prematurely, than the larger of $x$ $S_1$ or $x$ $T_1$ will determine the larger original expression. indeed, if $y = x$ $S_1$ and $z = x$ $T_1$, and $y > z$, then by the Lemma $y > 2z$, so since $y > 2m$, we have $y > z+m$. In our procedure we replace $x$ $S_1$ stack by plex$^y$ and $x$ $T_1$ stack by plex$^z$; since $y$ is more than $m$ more than $z$, plex$^y$ $S_2$ will be longer than plex$^z$ $T_2$, so the first expression will be larger. So we apply our procedure to $x$ $S_1$ and $x$ $S_2$; this will reduce the sum of the lengths by at least $m+2$, having used O(log m) operations.

So we wind up with an algorithm that takes O(n) operations.


We could extend the notation to have suffixes that apply k -> 10^^^k (Pent), k -> 10^^^^k (Hex), etc. I believe the obvious extension of the above procedure will work, e.g. for expressions with plex, bang, stack, and pent, first count the number of pents; the expression with more pents will be the larger. Otherwise, compare the n+1 groups of plex bang and stack lexicographically by our previously defined procedure. So long as the number of terms is less than googol-2, this procedure should work.

share|improve this answer
1  
Thank you for this answer! (+1) But could you kindly edit the opening of your answer to more accurately reflect the fact that you have not actually provided a general comparison algorithm? Your second part does not work, as you point out, when the number of operands becomes large. I believe that even among large terms with the same number of operands, the number of stacks does not always dominate, as it seems that googol bang${}^k$ will exceed googol stack plex${}^{k-1}$ for sufficiently large $k$, when the advantages of bang over plex allow it to overcome the stack. –  JDH Dec 19 '11 at 13:59
    
Since the readability of your answer will be greatly improved by the use of tex math notation, may I suggest that you or another user edit the answer to texify the mathematics? –  JDH Dec 19 '11 at 14:03
1  
Whew! Okay, I added TeX math notation where appropriate, and simplified the original proof so I only needed one long inequality. I also added a section where I described general comparison algorithm, which could be implemented in O(n) time. –  Deedlit Dec 22 '11 at 12:20
    
Note that googol bang^k < googol plex^{k+1} by my previous analysis, and the latter = (googol plex plex) plex$^{k-1}$ < googol stack plex$^{k-1}$. However, googol plex stack bang $^k$ stack will eventually exceed googol bang stack stack plex$^k$, so my restricted comparison algorithm does not work even for an even number of terms. Observe that to determine the minimum k for which the former dominates, we need to calculate googol bang - googol plex exactly. Since googol bang and googol plex could be replaced by anything, a comparison algorithm must be able to calculate arbitrary expressions. –  Deedlit Dec 22 '11 at 12:31
    
Deedlit, could you kindly send me an email? jhamkins@gc.cuny.edu –  JDH Jul 13 '12 at 23:57
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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