4 ms·
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 bou
by 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 agoSure, 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 agoThat 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.