5 ms·

Just because the difference between values is not computable does not mean that it grows faster than any computable function. The sequence iBB(n) = -1/BB(n) als

Just because the difference between values is not computable does not mean that it grows faster than any computable function. The sequence iBB(n) = -1/BB(n) also has incomputable deltas, but it grows more slowly than any increasing computable function. That’s not to say the entries aren’t large, I agree that they almost certainly are, but rather that the derivative is interesting in it’s own right, and making interesting statements about it is more difficult yet fun than guessing.

danbruc 3y ago
We know that asymptotically BB(n) > f(n) for every computable function f. Assume there is a computable upper bound d for the difference so that BB(n) - BB(n - 1) <= d(n). But now note that this gives you BB(n) <= d(1) + d(2) + ... + d(n) and that the right hand side is computable by assumption but that this contradicts the fact that there is no computable upper bound for BB(n). Therefore our assumption was incorrect, there is no computable upper bound for the differences, hence the differences themselves grow faster than any computable function.
- explaininjs 3y ago
  The assumption was indeed incorrect, but it was that there exists a computable upper bound d(n) for all n. My claim is that there may be a computable upper bound for some n. For instance it might be that particular d(n) values represent local maxima wherein a particular "mode" of computation is "unlocked" that uncomputably increases BB(n), leaving BB(n+ε) only computably greater for small natural numbers ε.
  - danbruc 3y ago
    Sure, that could potentially be the case. But as said before, I would argue that it does not seem unreasonable to me that you generally can increase BB(n) to twice BB(n) with one or a few additional states by slightly tweaking the machine. And that would be enough to get BB(n) - BB(n - 1) >= BB(n) which together with the size of BB(n) prevents really small differences. But I of course see that proving that you can increase the length of the output of any busy beaver by some constant using some number of additional states is far from trivial.
    - danbruc 3y ago
      That must of course be BB(n) - BB(n - 1) >= BB(n - 1). Also I have to retract the correction from a few comments ago, the currently best lower bound for BB(6, 2) is indeed 10 ⇈ 15, I looked at an outdated source when writing the correction.

danbruc 3y ago

We know that asymptotically BB(n) > f(n) for every computable function f. Assume there is a computable upper bound d for the difference so that BB(n) - BB(n - 1) <= d(n). But now note that this gives you BB(n) <= d(1) + d(2) + ... + d(n) and that the right hand side is computable by assumption but that this contradicts the fact that there is no computable upper bound for BB(n). Therefore our assumption was incorrect, there is no computable upper bound for the differences, hence the differences themselves grow faster than any computable function.

explaininjs 3y ago
The assumption was indeed incorrect, but it was that there exists a computable upper bound d(n) for all n. My claim is that there may be a computable upper bound for some n. For instance it might be that particular d(n) values represent local maxima wherein a particular "mode" of computation is "unlocked" that uncomputably increases BB(n), leaving BB(n+ε) only computably greater for small natural numbers ε.
- danbruc 3y ago
  Sure, that could potentially be the case. But as said before, I would argue that it does not seem unreasonable to me that you generally can increase BB(n) to twice BB(n) with one or a few additional states by slightly tweaking the machine. And that would be enough to get BB(n) - BB(n - 1) >= BB(n) which together with the size of BB(n) prevents really small differences. But I of course see that proving that you can increase the length of the output of any busy beaver by some constant using some number of additional states is far from trivial.
  - danbruc 3y ago
    That must of course be BB(n) - BB(n - 1) >= BB(n - 1). Also I have to retract the correction from a few comments ago, the currently best lower bound for BB(6, 2) is indeed 10 ⇈ 15, I looked at an outdated source when writing the correction.