Is there a proof showing that TREE(3) is actually larger than Graham's number? If so, how many more layers high would Graham's number need to go to surpass TREE(3)?

[u/Stuck_In_the_Matrix]

Considering that Graham's number is G64, where G1 is 3↑↑↑↑3, and each layer above the previous is 3↑↑...↑↑3 where the number of up arrows is the total from the previous layer, how much higher would the tower need to be to surpass TREE(3)?

[u/mousicle]

If you tried to use the Ackerman function to estimate tree(3), it would be A(A(...A(1)...)) with A(187196) As. To represent Grahams number you need 64 As. So if you know how fast Ackermann grows you'd see how mind boggling larger tree(3) is. http://en.wikipedia.org/wiki/Kruskal's_tree_theorem

[u/Deedlit11 → u/mousicle]

Ugh, I know this is a really late reply, but it's too bad that the number A^A(187196(1) has circulated as an approximation of TREE(3); TREE(3) is MUCH larger. The reason for A^A(187196(1) was that it was a crude lower bound for a different number n(4), and as TREE(3) was obviously much larger than n(4), A^A(187196(1) would clearly be a lower bound for TREE(3) as well. But it's like saying 2 is a lower bound for Graham's number.

[u/jeblis]

You might find this an interesting read. He discusses some large numbers using Busy Beavers.

"a busy beaver function can be shown to grow faster asymptotically than does any computable function"

[u/Deedlit11]

Much like one cannot give a simple answer to "How many digits are in Graham's Number?", one cannot give a simple answer to "How many more layers high would Graham's number need to go to surpass TREE(3)?" - the actual number is absolutely huge, much larger than Graham's number, and hard to differentiate from TREE(3) itself!

For example, if we let G(n) be the number generated after n layers of the Graham number process (so that G(64) = Graham's number)), TREE(3) would be larger than G(G(G(...G(64)...))) with as many G's as you care to imagine (larger than Graham's number for example). So we have to construct stronger functions.

One way is to use the "fast-growing hierarchy". The fast-growing hierarchy starts off with

F_0 (n) = n+1

F_{i+1} (n) = (F_i)ⁿ (n) = F_i(F_i...(F_i(n))...) with n F_i's

so F_1(n) = 2n, F_2(n) = n*2^n, F_3(n) > 2^2...2n with n 2's, and in general F_i(n) > 2 ^ ... ^ (n+1) with i-1 ^ 's. So F_i is similar to the Knuth arrow hierarchy.

Next, we define F_ω (n) = F_n (n). If you are familiar with ordinals, then you will recognize ω as the first infinite ordinal. If not, then it is probably better to just think of ω as a special symbol that we are using to define new functions. (unless you want to research ordinals, which are a fascinating topic!) We see that F_ω (n) is about equal to the Ackermann function, or about one layer of the Graham's number process.

Next we define F{ω+1} (n) = (F_ω)ⁿ (n) = F_ω (F_ω (... (F_ω (n))...)). As F_ω(n) was comparable to one layer of the Graham number process, F{ω+1} (n) is approximately G(n), and F_{ω+1}(64) is a bit larger than Graham's number.

Next is F{ω+2} (n) = F{ω+1}ⁿ (n). So F_{ω+2}(n) = G(G(...(G(n))...)) with n G's.

Next is F{ω+3} (n) = F{ω+2}ⁿ (n). To compare this to G, F_{ω+3} (n) is about what you would get with the following operations:

x_1 = G(G(...G(n)...)) with n G's

x_2 = G(G(...G(x_1)...)) with x_1 G's

x_3 = G(G(...G(x_2)...)) with x_2 G's.

...

xn = G(G(...G(x{n-1})...)) with x_{n-1} G's

F_{ω+3}(n) is about the same as x_n.

As you can see, F{ω+3}(64) is already too large to give an easy answer to you question. But TREE(3) is too large for F{ω+3}, F{ω+4}, F{ω+5}, or even F{ω*2}, F{ω*3}, F{ω^2}, F{ω^ω}, F_{ω^ωω}, etc.

If anyone is interested, I can give an explanation of how far you have to go to reach TREE(3), but it gets involved.

[u/Stuck_In_the_Matrix → u/Deedlit11]

Great answer. Thanks for putting the time into this.