# Is there any pratical use to really large number mathematics (e.g. Graham's Number or Tree(3))?

**URL:** <https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958>\
**Category:** Factual Questions\
**Created:** [November 4, 2018, 3:18am UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958 "2018-11-04T03:18:23Z")\
**Posts on this page:** 12\
**Page:** 3

<div class="post-metadata">

**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\
**Post date:** [November 12, 2018, 8:57pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/41 "2018-11-12T20:57:01Z")

</div>

> [@Velocity](#):
>
> Also, how do they prove numbers like TREE3 and Rayo’s and Loader’s number are finite?

Rayo’s number, the biggest one, is easiest to check: using a fixed number of symbols (10[sup]100[/sup]), one can describe only finitely many numbers, so there is an upper bound.

Loader’s number IIRC relies on the fact that every term in a particular typed lambda calculus is strongly normalizing; in other words we essentially have a programming language in which every program terminates, so Loader’s program can simply loop over all programs up to a certain length and collect the results.

TREE(3) follows from Kruskal’s tree theorem that the set of all trees is quasi-well ordered by the rule that T ≤ T’ if and only if T can be homeomorphically embedded into T’. (Labelled) trees being well-quasi-ordered means that for any infinite sequence T[sub]1[/sub], T[sub]2[/sub], … there is some i \< j for which T[sub]i[/sub] ≤ T[sub]j[/sub]. This implies that given, say, 3 labels, there is an evidently ludicrously long, but still finite, maximal length of a sequence of rooted, labelled trees where T[sub]i[/sub] has at most i vertices and no tree embeds into any tree later in the sequence. There is a short proof of Kruskal’s tree theorem by Crispin Nash-Williams which starts by choosing a bad sequence of trees with T[sub]1[/sub], then T[sub]2[/sub], T[sub]3[/sub], … having the minimal number of vertices, then showing this leads to a contradiction.

> [@Velocity](#):
>
> Is there a way to find the last few digits of TREE3 like there is to get the last hundred digits of Graham’s number?

I don’t see how; it’s not like you are exponentiating anything. In theory you could run a program to compute the number, but you cannot actually successfully run such a program on any actual computer.

---

<div class="post-metadata">

**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\
**Post date:** [November 12, 2018, 9:09pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/42 "2018-11-12T21:09:05Z")

</div>

> [@septimus](#):
>
> No connection. Except that just as Graham’s Number is a ridiculously large _finite_ number, so the Woodin cardinals are ridiculously large _infinities_. My “Any Woodin Cardinal would have to be greater than ℵ[sub]G[/sub]” was just a (very poor) way to allude to that.

May as well point out it’s larger than ℵ[sub]ω[/sub], larger than ℵ[sub]ω[sup]ω[/sup][/sub], etc. 🙂

---

<div class="post-metadata">

**Author:** ![Velocity](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/velocity/32/18006_2.png) [@Velocity](https://boards.straightdope.com/u/Velocity)\
**Post date:** [November 12, 2018, 9:12pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/43 "2018-11-12T21:12:17Z")

</div>

> [@DPRK](#):
>
> Rayo’s number, the biggest one, is easiest to check: using a fixed number of symbols (10[sup]100[/sup]), one can describe only finitely many numbers, so there is an upper bound.
> 
> Loader’s number IIRC relies on the fact that every term in a particular typed lambda calculus is strongly normalizing; in other words we essentially have a programming language in which every program terminates, so Loader’s program can simply loop over all programs up to a certain length and collect the results.
> 
> TREE(3) follows from Kruskal’s tree theorem that the set of all trees is quasi-well ordered by the rule that T ≤ T’ if and only if T can be homeomorphically embedded into T’. (Labelled) trees being well-quasi-ordered means that for any infinite sequence T[sub]1[/sub], T[sub]2[/sub], … there is some i \< j for which T[sub]i[/sub] ≤ T[sub]j[/sub]. This implies that given, say, 3 labels, there is an evidently ludicrously long, but still finite, maximal length of a sequence of rooted, labelled trees where T[sub]i[/sub] has at most i vertices and no tree embeds into any tree later in the sequence. There is a short proof of Kruskal’s tree theorem by Crispin Nash-Williams which starts by choosing a bad sequence of trees with T[sub]1[/sub], then T[sub]2[/sub], T[sub]3[/sub], … having the minimal number of vertices, then showing this leads to a contradiction.  
> I don’t see how; it’s not like you are exponentiating anything. In theory you could run a program to compute the number, but you cannot actually successfully run such a program on any actual computer.

yey!

---

<div class="post-metadata">

**Author:** ![ricksummon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ricksummon/32/3333_2.png) [@ricksummon](https://boards.straightdope.com/u/ricksummon)\
**Post date:** [November 13, 2018, 12:51am UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/44 "2018-11-13T00:51:01Z")

</div>

Is it even possible to describe TREE(3) with any known kind of mathematical notation? You can do this with Graham’s number using Conway chained arrow notation:

g(1) = 3-\>3-\>4, g(N) = 3-\>3-\>g(N-1), G = g(64)

But how can we even know _how_ big TREE(3) is in comparison to other large numbers?

---

<div class="post-metadata">

**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\
**Post date:** [November 13, 2018, 2:03am UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/45 "2018-11-13T02:03:21Z")

</div>

> [@ricksummon](#):
>
> But how can we even know _how_ big TREE(3) is in comparison to other large numbers?

The “Googolology Wiki” states that [Adam P. Goucher](https://cp4space.wordpress.com/2012/12/19/fast-growing-2/) has [demonstrated](https://mathoverflow.net/questions/93828/how-large-is-tree3) that TREE(n) grows at least as fast as f[sub]ϑ(Ω[sup]ω[/sup]ω)/sub in the [fast-growing hierarchy](https://en.wikipedia.org/wiki/Fast-growing_hierarchy) (he alludes to [constructions](https://cs.nyu.edu/pipermail/fom/2006-March/010260.html) by Friedman of long lists of trees) – I haven’t gone through any of this carefully, but if we accept the general principle then given a certain degree of effort it is possible to put at least rough bounds on some of these functions and compare their growth rates. Graham’s number is less than f[sub]ω+1/sub, for example.

---

<div class="post-metadata">

**Author:** ![pjd](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pjd/32/3009_2.png) [@pjd](https://boards.straightdope.com/u/pjd)\
**Post date:** [November 14, 2018, 7:40pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/46 "2018-11-14T19:40:49Z")

</div>

I don’t know nuffink about big numbers, but this thread led me to find this …  
[The colossal book of mathematics](http://www.logic-books.info/sites/default/files/the_colossal_book_of_mathematics.pdf)

so thanks !

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [November 15, 2018, 2:58pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/47 "2018-11-15T14:58:23Z")

</div>

I always considered than the main result of many papers I wrote wasn’t the new facts in the paper, but the new methods developed to establish those facts.

A lot of “not practical” Mathematical techniques have been used to establish quite practical results. Take Cantor’s diagonalization. What’s the practical value of knowing that there are more reals than integers?

But diagonalization has been used to establish the complexity of classes of computation. E.g., we know that there are problems that require quadratic time. If your problem is complete for quadratic time, that’s it. You know it can’t be done faster.

Similarly a lot of other obtuse methods have been used in more mundane scenarios. E.g., Cohen’s [forcing](https://en.wikipedia.org/wiki/Forcing_(mathematics)) technique.

People are fascinated with the Tree function since it’s amazing how complex you can get with so little to start with. I think that people will be coming up with tiny variations of Tree that grow at more reasonable rates giving categories of functions that represent useful complexity classes and therefore can lead to new insights into those classes and how they relate.

---

<div class="post-metadata">

**Author:** ![ricksummon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ricksummon/32/3333_2.png) [@ricksummon](https://boards.straightdope.com/u/ricksummon)\
**Post date:** [November 15, 2018, 7:24pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/48 "2018-11-15T19:24:34Z")

</div>

Is TREE a computable function? The information I’ve found seems to indicate it is. If so, that means the Busy Beaver function must exceed it starting at some value N. Is it even possible to guess what that value of N might be?

---

<div class="post-metadata">

**Author:** ![Colophon](https://avatars.discourse-cdn.com/v4/letter/c/f05b48/32.png) [@Colophon](https://boards.straightdope.com/u/Colophon)\
**Post date:** [November 15, 2018, 8:05pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/49 "2018-11-15T20:05:54Z")

</div>

My wife uses Graham’s number as some kind of spending goal.

---

<div class="post-metadata">

**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\
**Post date:** [November 15, 2018, 9:06pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/50 "2018-11-15T21:06:51Z")

</div>

There you go, **ricksummon** , you may have just laid the groundwork for defining some new ultralarge number.

---

<div class="post-metadata">

**Author:** ![ricksummon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ricksummon/32/3333_2.png) [@ricksummon](https://boards.straightdope.com/u/ricksummon)\
**Post date:** [November 15, 2018, 9:14pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/51 "2018-11-15T21:14:41Z")

</div>

I answered my own question: **TREE(n)** is definitely a computable function, since you could have a simple algorithm to generate trees and check to see if any of them are imbeddable into later trees. You couldn’t _really_ compute it, but you could with an idealized computer with infinite computing time and storage.

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [November 15, 2018, 9:19pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/52 "2018-11-15T21:19:26Z")

</div>

> [@ricksummon](#):
>
> Is TREE a computable function? The information I’ve found seems to indicate it is. If so, that means the Busy Beaver function must exceed it starting at some value N. Is it even possible to guess what that value of N might be?

A quick check shows that it’s been proven that Graham’s number is \<= BB(64) but that is no doubt a horrible upper bound. Turns out there’s a whole [site](http://googology.wikia.com/wiki/Busy_beaver_function) devoted to these sort of things.

So one practical aspect: It generates a place for large number nerds to hang out. (From their home page: “We have reached 0% of our goal of 10[sup]100[/sup] articles!” I assumed they rounded the 0%.)

[Previous page](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958.md?page=2)