I just read these excellent lecture notes by Scott Aaronson, and I found the second homework problem at the end to be incredibly thought-provoking (this course was offered over ten years ago, so I think it's now safe to discuss the homework online):
Let BB(n), or the "nth Busy Beaver number," be the maximum number of steps that an n-state Turing machine can make on an initially blank tape before halting. (Here the maximum is over all n-state Turing machines that eventually halt.)
- Prove that BB(n) grows faster than any computable function.
- Let S = 1/BB(1) + 1/BB(2) + 1/BB(3) + ... Is S a computable real number? In other words, is there an algorithm that, given as input a positive integer k, outputs a rational number S' such that |S-S'|<1/k?
I understand question #1 - it's #2 I'm wondering about. Clearly the series converges, since the sequence $1/BB(n)$ falls off much faster than $1/n$ (to put it mildly...). I suspect that $S$ in uncomputable like Chaitin's constant. (Although in some vague sense S seems to me to be more "natural," because it does not rely on a specific choice of prefix-free universal computable function "programming language" - so perhaps it's more analytically tractable?) Am I correct?
Also, is there anything at all that we can say about $S$ quantitatively? (Beyond the trivial result that it's greater than $1/4 + 1/6 + 1/13 = 77/156 = 0.494...$ based on the known values of $BB(2)$, $BB(3)$, and $BB(4)$.)
Edit: The solution is on pg. 43 of Quantum Computing Since Democritus. The answer is that $S$ is uncomputable and the reasoning is similar to mercio's, except instead of comparing $\mathrm{BB}(n)$ to a specific exponential sequence, there's just the vague sentence
Since $1/\mathrm{BB}(n+1)$, $1/\mathrm{BB}(n+2)$, and so on are so much smaller than $1/\mathrm{BB}(n)$, any upper bound on $1/S_n$ immediately yields an upper bound on $\mathrm{BB}(n)$ as well.
What is a precise upper bound?