2
$\begingroup$

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$?

$\endgroup$
  • 5
    $\begingroup$ The answer is no; it is way, way bigger than the humble power tower can reach in a reasonable way. There are loads of descriptions about how to write an expression for Graham's number using Knuth arrow notation, e.g. described on the wikipedia page which should make it clear that the power tower is completely inadequate. $\endgroup$ – Thompson Sep 26 '16 at 15:55
  • $\begingroup$ The wikipedia page on Graham's number states: "As with these, it is so large that the observable universe is far too small to contain an ordinary digital representation of Graham's number, assuming that each digit occupies one Planck volume, possibly the smallest measurable space. Even power towers [e.g. your $x^{x^{x^{⋰^x}}}$] are insufficient for this purpose, ..." $\endgroup$ – TastyRomeo Sep 26 '16 at 15:57
  • $\begingroup$ The much,much,much,much,much smaller number $$N:=3\uparrow\uparrow\uparrow\uparrow 3$$ is already not expressible with a power tower with a "reasonable" height and a "reasonable" large $x$. To get this number , denote $n:=3\uparrow \uparrow 3^{27}$ (This is a power tower of $3$'s with height $3^{27}$). Now start with $a_1=3$ , $a_2=3\uparrow\uparrow 3=3^{3^3}$ , $a_3=$a power tower of 3's with height $a_2$ and so on (we iterate the height of the power tower!). Step $n$ is $N$ and it is absolutely nothing compared to Graham's number. $\endgroup$ – Peter Dec 22 '16 at 21:50
  • $\begingroup$ Perhaps unexpectedly, the value of $x$ has less effect than the value of $n$, but as everyone is saying, Graham's number is not reasonably expressible by this method. $\endgroup$ – Joffan Mar 4 '17 at 1:49
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ For my sanity, I prefer to use $\uparrow^n=\uparrow\uparrow\dots\uparrow$ :-) And inconceivably huge, as always, is a relative term. $\endgroup$ – Simply Beautiful Art Mar 4 '17 at 2:11
  • 1
    $\begingroup$ @SimplyBeautifulArt Inconceivable! $\endgroup$ – Noah Schweber Mar 4 '17 at 2:18
  • $\begingroup$ Lol, old memories and strange moments. $\endgroup$ – Simply Beautiful Art Oct 14 '17 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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