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

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

F0 (n) = n+1 F{i+1} (n) = (F_i)n (n) = F_i(F_i...(F_i(n))...) with n F_i's

so F_1(n) = 2n, F_2(n) = n*2n, F_3(n) > 22...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 (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 (n). So F_{ω+2}(n) = G(G(...(G(n))...)) with n G's.

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

x1 = 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. ... x_n = 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}, F2}, 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.

/r/askscience Thread