[Cross-posted from Math SE - apologies if this is not appropriate.]
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)$.)