6
$\begingroup$

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

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?

$\endgroup$
3
  • 1
    $\begingroup$ The busy-beaver function does depend on a choice of way to assign sizes to machines, which is in a sense as arbitrary as the choice of language for Chaitin's constant. It is conventional to count states in a particular kind of Turing machine, but the beaver would be just as busy if the argument was instead, say, a bound for the number of characters in a Scheme program. $\endgroup$
    – hmakholm left over Monica
    Jul 7, 2017 at 10:44
  • $\begingroup$ @HenningMakholm This is a fair point. It seems to me that the $n$-state, 2-symbol Turing machine is the most "simple/natural" way to assign sizes to machines, and also produces the slowest-growing possible BB sequence and hence the largest possible value of $S$, but maybe that's just because I haven't thought much about alternate models of universal computation. But if nothing else, this is probably the easiest BB sequence to calculate as a practical matter, because theoretical computer scientists have developed a lot more formal tools to work with Turing machines than with Scheme programs. $\endgroup$
    – tparker
    Jul 7, 2017 at 15:22
  • $\begingroup$ x @tparker: I mentioned Scheme because that's a pretty clean programming language with a strong theoretical basis. Perhaps instead I should have invoked the lambda-calculus directly -- I don't think a BB function giving "the size of the largest $\beta$-normal form of any closed lambda term of size $n$" or "length of longest CBV reduction to head normal form" would be less convenient to work with than one based on Turing machines, and certainly not for lack of formal machinery to reason about lambda terms! $\endgroup$
    – hmakholm left over Monica
    Jul 7, 2017 at 15:33

1 Answer 1

Reset to default
5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ In your third sentence, I think you mean "an upper bound on the remainder of the series"? $\endgroup$
    – tparker
    Jul 7, 2017 at 16:10
  • 1
    $\begingroup$ Very clever! But I'm not sure if I agree with your initial assumption: $BB(n+h) \geq 2\, BB(n)$ for some integer $h$, but how do we know that $h$ is computable (I assume that's what you mean by "effective")? $\endgroup$
    – tparker
    Jul 7, 2017 at 16:42
  • $\begingroup$ Note that you only need some $h$ for which this is true, not the minimum possible $h$. One constructive way you can find such an $h$ is show how to transform an n-state Turing machine T into an (n+h)-state Turing machine T' which runs T twice; this immediately would imply that $BB(n+h) \geq 2BB(n)$. $\endgroup$
    – jschnei
    Jul 7, 2017 at 19:04
  • $\begingroup$ "We all know" that $BB(n)$ grows quickly enough that $BB(n+1) \gt 2BB(2)$ so you can use $h=1$ $\endgroup$
    – Ross Millikan
    Mar 17, 2018 at 17:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .