Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Probably a proof (if any exist) that calls upon Knuth's up-arrow notation or Busy Beaver.

share|improve this question
6  
Once upon a time, this was Graham's number: en.wikipedia.org/wiki/Graham's_number. I have no idea what the answer is now. –  Qiaochu Yuan Aug 15 '10 at 4:44
2  
This should be community wiki. Perhaps closed –  Casebash Aug 15 '10 at 6:34
2  
Infinity $\infty$ is used in lots of proofs :) Anything bigger? –  Pratik Deoghare Aug 16 '10 at 13:05
1  
I once saw a programming contest along the following lines: Write a C program, under 5K bytes, that outputs the biggest number possible. Assume (contrary to fact) that C can handle arbitrarily large integers and that your program has unlimited computational resources (i.e. memory). The winning entries were amazing. –  Frank Thorne Aug 10 '12 at 18:51
1  
@Casebash: There is a unique answer to the question, so I do not see why it should be a community wiki. –  user1729 Sep 19 '12 at 11:06

4 Answers 4

up vote 10 down vote accepted

The mathematician Harvey Friedman observed a special finite form of Kurskal's Tree Theorem. Regarding this form, Friedman discusses the existence of a rapidly growing function he calls $TREE(n)$.

The $TREE$ sequence begins $TREE(1)=1$ and $TREE(2)=3$, but $TREE(3)$ is a number so extremely large that its weak lower bound is $(A(...A(1)...))$, where the number of A's is $A(187196)$, and $A()$ is a version of Ackermann's function: $A(x) = 2↑↑...↑x$ with $x-1 ↑s$ (Knuth up-arrows).

Whereas Graham's Number is $A^{64}(4)$, the above mentioned lower bound is $A^{A(187196)}$. As you can imagine, the $TREE$ function keeps on growing rather quickly. For a discussion on the hierarchy of fast growing functions see here: http://en.wikipedia.org/wiki/Fast-growing_hierarchy

There are other examples of numbers greater than Graham's Number, as can be seen here: http://en.wikipedia.org/wiki/Goodstein_function#Sequence_length_as_a_function_of_the_starting_value, although I'm not sure if this number is larger than Friedman's $TREE(3)$

share|improve this answer

TREE[3] is much larger than the numbers derived from Goodstein sequences for any reasonable input. See: http://www.cs.nyu.edu/pipermail/fom/2006-March/010279.html

The Goodstein function is upper bounded by ε₀, whereas the TREE function is lower bounded by the small Veblen ordinal.

share|improve this answer

BB(n) can surpass any recursive number, it is not computable. Perhaps, BB(1000) already inexpressible in any existing notation. You can also: BB(BB(n)), BB(BB(BB(...(BB(n))...)) (with "n" nested functions).

share|improve this answer
6  
Correct, but the question asked for a specific number, used in a proof. Do you know of a proof where BB(1000) appears? –  Rick Decker Sep 21 '12 at 18:30

In one of Friedman's posts on the FOM mailing list, he mentions a number called SCG(13) that is far larger than TREE(3): http://www.cs.nyu.edu/pipermail/fom/2006-April/010362.html

I couldn't find a lot of other information about it, though.

share|improve this answer

protected by Community May 6 at 9:18

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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