Since logarithms are monotonically increasing, you can determine if $$a^b > c^d$$ by instead checking if $$\log(a^b) > \log(c^d)$$ which can be rewritten (using basic properties of logarithms) as $$b\log(a) > d\log(c)$$ This results in the comparison of two numbers on the order of those given in the input (that is, both numbers will be within an order of magnitude or so of $a,b,c,d$), which is definitely feasible on a computer.
You can also use logs to calculate other properties, as long as you remember to convert your solution back to the original numbers (by means of an exponential) when you're done. For example, to compute whether $${a_1}^{b_1}{a_2}^{b_2} > {c_1}^{d_1}{c_2}^{d_2}$$, you can take the log of both sides to get
\begin{align}
\log({a_1}^{b_1}{a_2}^{b_2}) &> \log({c_1}^{d_1}{c_2}^{d_2}) \\
\log({a_1}^{b_1}) + \log({a_2}^{b_2}) &> \log({c_1}^{d_1}) + log({c_2}^{d_2}) \\
b_1\log(a_1) + b_2\log(a_2) &> d_1\log(c_1) + d_2\log(c_2) \\
\end{align}
which is again computationally feasible.
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.
Best Answer
Basically you want to construct a chain of inequalities that links the smaller expression to the larger expression. Induction is often helpful in these cases.
A useful theorem for Knuth arrows is $(a \uparrow^n b) \uparrow^n c < a \uparrow^n (b+c)$, proven in this paper. It is also proven that $a \uparrow^n c$ is monotonic in $a,n$, and $c$ when $a,c \ge 3$, which is useful as well.
For example, one can easily see that $S < 3 \uparrow\uparrow 6$, so
$$S^{S^{S^\cdots}} = S \uparrow \uparrow S < (3\uparrow\uparrow 6)\uparrow\uparrow(3 \uparrow\uparrow 6) < 3\uparrow\uparrow (6 + 3\uparrow\uparrow 6) < 3 \uparrow\uparrow (3 \uparrow\uparrow 7) < 3 \uparrow\uparrow (3\uparrow\uparrow 3^{3^3}) = 3 \uparrow\uparrow (3\uparrow\uparrow\uparrow 3) = 3\uparrow\uparrow\uparrow 4 < 3\uparrow\uparrow\uparrow (3 \uparrow\uparrow\uparrow 3) = 3\uparrow\uparrow\uparrow\uparrow 3 = G_1$$
To address your harder question, first we need to know what $G(0,y)$ is. Since we need $G(0,3) =4$ so that $G(64,3)$ is Graham's number, I will assume that $G(0,y)=4$.
Theorem: $G(n,S) < G(n+1,3)$
We will prove this by induction. First, observe that $G(0,S) = 4 < 3\uparrow\uparrow\uparrow\uparrow 3 = G(1,3)$.
Observe that for $n \ge 3$,
$$S \uparrow^n S < (3\uparrow\uparrow 6)\uparrow^n (3\uparrow\uparrow 6) < (3\uparrow^n 6)\uparrow^n (3\uparrow\uparrow 6) < 3\uparrow^n (6+3\uparrow\uparrow 6) < 3\uparrow^n (3\uparrow\uparrow\uparrow 3) \le 3\uparrow^n (3\uparrow^n 3) = 3\uparrow^{n+1} 3$$
So if we have $G(n,S) < G(n+1,3)$, then $G(n,S)+1 \le G(n+1,3)$, so
$$G(n+1,S) = S \uparrow^{G(n,S)} S < 3 \uparrow^{G(n,S)+1} 3 \le 3 \uparrow^{G(n+1,3)} 3 = G(n+2,3)$$
and the theorem follows by induction.
So in particular, $G(60,S) < G(61,3) < G(64,3)$.