10 ms·

I agree intuitively, but do you have a formal proof of such? This thread seems to struggle to find one: https://news.ycombinator.com/item?id=38121507 https://ne

I agree intuitively, but do you have a formal proof of such? This thread seems to struggle to find one: https://news.ycombinator.com/item?id=38121507 https://news.ycombinator.com/item?id=38121507

danbruc 3y ago
First a correction, I got the lower bound for BB(6, 2) wrong, what I quoted is the runtime, the number of ones is only 10^18267 which is tiny compared to the number of permutations of the particles in the observable universe. I think proofing a good estimate of the difference will be hard to impossible. We have lower bounds but by definition we can not have a computable upper bound, at least not for arbitrary n. But we need both because we would have to find the difference between the lower bound for BB(748) and the upper bound for BB(745) in order to get an lower bound on the difference between the two. So yes, in principle the difference BB(748) - BB(745) could be small, but given that the difference BB(n) - BB(n - 1) itself grows faster than any computable function [1] that would be quite surprising. Which is of course a terrible argument. For BB(748) we have three additional states that we can use to modify the machine for BB(745). And it does not seem completely implausible that we could kind of stretch one state transition, instead of going from state A to state B writing one 1 we go through one of the additional states in between and write another one, writing twice as many 1s as before. But finding a general construction that provably works for all relevant Turing machines is probably at least not trivial and might as well be impossible. But if one could show this, then we would get something like BB(748) >= 2 * BB(745) and therefore BB(748) - BB(745) >= BB(745). And this we could then combine with a lower bound for BB(745). [1] If it would not, we could have a computable upper bound for the differences BB(n) - BB(n - 1) which we could turn into a computable upper bound for BB(n) by just summing the bound for the differences up to n.
- explaininjs 3y ago
  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.

I agree intuitively, but do you have a formal proof of such? This thread seems to struggle to find one: https://news.ycombinator.com/item?id=38121507 https://news.ycombinator.com/item?id=38121507

danbruc 3y ago

First a correction, I got the lower bound for BB(6, 2) wrong, what I quoted is the runtime, the number of ones is only 10^18267 which is tiny compared to the number of permutations of the particles in the observable universe. I think proofing a good estimate of the difference will be hard to impossible. We have lower bounds but by definition we can not have a computable upper bound, at least not for arbitrary n. But we need both because we would have to find the difference between the lower bound for BB(748) and the upper bound for BB(745) in order to get an lower bound on the difference between the two. So yes, in principle the difference BB(748) - BB(745) could be small, but given that the difference BB(n) - BB(n - 1) itself grows faster than any computable function [1] that would be quite surprising. Which is of course a terrible argument. For BB(748) we have three additional states that we can use to modify the machine for BB(745). And it does not seem completely implausible that we could kind of stretch one state transition, instead of going from state A to state B writing one 1 we go through one of the additional states in between and write another one, writing twice as many 1s as before. But finding a general construction that provably works for all relevant Turing machines is probably at least not trivial and might as well be impossible. But if one could show this, then we would get something like BB(748) >= 2 * BB(745) and therefore BB(748) - BB(745) >= BB(745). And this we could then combine with a lower bound for BB(745). [1] If it would not, we could have a computable upper bound for the differences BB(n) - BB(n - 1) which we could turn into a computable upper bound for BB(n) by just summing the bound for the differences up to n.

explaininjs 3y ago
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.