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$

closed as off-topic by D.W. Oct 12 '17 at 1:56

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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