1
$\begingroup$

[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.)

  1. Prove that BB(n) grows faster than any computable function.
  2. 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)$.)

$\endgroup$
  • $\begingroup$ On the Math SE post, mercio proved that $S$ is uncomputable assuming that $BB(n+h) \geq 2BB(n)$ for some computable integer $h$. While such an $h$ exists, I'm not convinced that it's computable. And anyway, I'm more interested in the question in my last paragraph. $\endgroup$ – tparker Oct 12 '17 at 1:00
  • $\begingroup$ Math.SE well, in fact cross-posting is not allowed, probably it should be flagged for migration. $\endgroup$ – Evil Oct 12 '17 at 1:36
  • $\begingroup$ Cross-posted: math.stackexchange.com/q/2349229/14578, cs.stackexchange.com/q/82346/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. Perhaps you can identify a more specific, narrow question that's different from what you previously posted on Math.SE, and ask that? $\endgroup$ – D.W. Oct 12 '17 at 1:56
  • $\begingroup$ I'm voting to close this question because it was cross-posted. $\endgroup$ – D.W. Oct 12 '17 at 1:56
  • $\begingroup$ @D.W. Do you think this question is more appropriate for Math or CS SE? $\endgroup$ – tparker Oct 12 '17 at 2:35