Solution of $x^{{x^{⋰^{x}}}} \approx$ Graham's Number?

Question

This is not a homework, just something I am curious about. There are two independent variables in this problem: $x$, and $n$, the number of $x$'s. I am wondering if it is possible to express Graham's number with "reasonable" values for $x$ and $n$, say, $x \le$ a trillion, and $n\le 6$? If no, how much loser do the bounds need to be on $x$ and $n$?

Answer 1

The answer is "no", where we define "reasonable" as something with

$$x,n<10^{10}$$

which is more than you asked for.

Let's start with a conversation on Knuth's up-arrow notation. It's rather simple really:

$$a\uparrow^1b=a\uparrow b=a^b$$

Then,

$$a\uparrow^2b=a\uparrow\uparrow b=\underbrace{a\uparrow(a\uparrow(a\uparrow(\dots\uparrow a}_{\text{b amount of a's}})))$$

Note the parenthesis.

$$a\uparrow^3b=a\uparrow\uparrow\uparrow b=\underbrace{a\uparrow\uparrow(a\uparrow\uparrow(a\uparrow\uparrow(\cdots\uparrow\uparrow a}_{\text{b amount of a's}}\cdots)))$$

etc. It should be fairly clear that

$$x^{x^{x^{\dots}}}=x\uparrow^2n\le(10^{10})\uparrow^2(10^{10})$$

You probably think this is large, but on the contrary,

$$G1=3\uparrow^43$$

To get an idea of how large $G1$ is, note that

$$3\uparrow^23=3^{3^3}=3^{27}\approx7.6\text{ trillion}$$

$$3\uparrow^33=3\uparrow^2(3\uparrow^23)=3\uparrow^27.6\text{ trillion}\\=\underbrace{3\uparrow(3\uparrow(\cdots\uparrow3}_{7.6\text{ trillion}}\cdots))$$

Of course, the upper bound to your "reasonable numbers" beats this, but its a little sketchy whether or not it is larger than $G1$. I wish to clear this concern:

$$3\uparrow^43=3\uparrow^3[\underbrace{3\uparrow(3\uparrow(\cdots\uparrow3}_{7.6\text{ trillion}}\cdots))]\\=\underbrace{3\uparrow^2(3\uparrow^2(\dots\uparrow^23}_{\underbrace{3\uparrow(3\uparrow(\cdots\uparrow3}_{7.6\text{ trillion}}\dots))}\cdots))$$

If you think about this and you start to lose focus on what this all means, remember that

$$3\uparrow^23=7.6\text{ trillion}$$

$$3\uparrow^2(3\uparrow^23)=\underbrace{3\uparrow(3\uparrow(\cdots\uparrow3}_{7.6\text{ trillion}}\cdots))=3^{3^{3^{\dots}}}\bigg\}7.6\text{ trillion }3's$$

$$3\uparrow^2(3\uparrow^2(3\uparrow^23))=\underbrace{3\uparrow(3\uparrow(\dots\uparrow3}_{\underbrace{3\uparrow(3\uparrow(\cdots\uparrow3}_{7.6\text{ trillion}}\dots))}\cdots))=3^{3^{3^{\dots}}}\bigg\}\text{give up on counting how many }3's$$

Indeed, the shear amount of $3$'s is staggering, and by $3\uparrow^35$, your upper bound can no longer compare.

And this is only a small step towards Graham's number. Note that

$$G2=3\uparrow^{G1}3$$

which is probably unimaginably large, but then...

$$G(n+1)=3\uparrow^{G(n)}3$$

and $G64$ is the famed Graham's number.

---

But of course, this is only one small step for large numbers. It is quite easy to produce numbers larger than Graham's number in a hundred characters of code. Once you've got Graham's number down, you can go ahead and do the following:

$$\underbrace{G(G(G(\cdots G(}_{1\text{ million }G's}64)\cdots)))$$

or

$$\underbrace{G(G(G(\cdots G(}_{\underbrace{G(G(G(\cdots G(}_{\underbrace{G(G(G(\cdots G(}_{\vdots}64)\cdots)))~G's}64)\cdots)))~G's}64)\cdots)))$$

And these are still rather small :-) Relatively of course.

---

If you do go happening to look at how to compare numbers of these sizes, I recommend spending some time browsing the Googology Wiki, and to learn Fast Growing Hierarchy (FGH), a function that sizes well against large numbers.

Answer 2

To move this off the unanswered list: no, you cannot.

The expression you're talking about is just $x\uparrow\uparrow n$, in the up-arrow notation. Now, Graham's number is defined using this notation, but with an additional twist - just as the uparrow notation itself is recursive, we define Graham's number via a recursive use of uparrows. Namely, we define a sequence of numbers as follows:

• $a_1=3\uparrow\uparrow\uparrow\uparrow 3$. Note that this is already gigantic - it's not hard too show that this is more than trillion$\uparrow\uparrow$trillion. To get a sense for this, note that $3\uparrow\uparrow 3$ is already $3^{27}$, which is about seven trillion. $3\uparrow\uparrow\uparrow 3$ is then incredibly huge - it's vastly larger than $3\uparrow\uparrow (7\cdot 10^{12})$, which is an exponential tower of seven trillion $3$s.

• Having defined $a_i$, we let $a_{i+1}$ be the number $3\uparrow...\uparrow 3$, where the number of $\uparrow$s is $a_i$. So, e.g., $a_2$ has more than trillion$\uparrow\uparrow$trillion uparrows!

• Then Graham's number is $a_{64}$.

This is impossibly, inconceivably huge. Even the uparrow notation is insufficient for describing it directly - if each uparrow took exactly one molecule of space to write, it would take more than the volume of the observable universe to write the number of uparrows used in the definition of $a_2$.