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?
I assume that you can prove constructively $BB(n+1) \ge BB(n)$ and $BB(n+h) \ge 2 BB(n)$ for some effective integer $h$.
Then if the sum was computable, you would be able to compute $BB(n)$ for every $n$ :
Since we know $BB(n)$ grows at least kinda exponentially, this allows us to turn a lower bound on the remainder of the series into an upper bound for $BB(n)$ :
$\sum_{k \ge n} 1/BB(k) \le (\sum_{n \le k < n+h} 1/BB(n)) (1+2^{-1}+2^{-2}+\ldots) \le 2h/BB(n)$.
And thus if $a \le \sum_{k \ge n} 1/BB(k)$ then $BB(n) \le 2h/a$.
Now you can compute every $BB(n)$ by induction.
Suppose you know exactly the first $(n-1)$ values. Use your magical algorithm until you get a statement $\sum_{k \ge 1} 1/BB(k) \ge \sum_{1 \le k < n} 1/BB(k) + a$ for some $a > 0$.
Then you get $BB(n) \le 2h/a$. Since you have an upper bound on $BB(n)$ you can compute it by running every $n$-state Turing machine for that many steps.