5 ms·

A commonly quoted number for the number of particles in the observable universe is 10^80 give or take a few orders of magnitude an they have very roughly 10^10^

A commonly quoted number for the number of particles in the observable universe is 10^80 give or take a few orders of magnitude an they have very roughly 10^10^10^2 permutations if you consider all particles distinguishable. The best known lower bound for BB(6, 2) seems to be 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 which is more like the number of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of the particles in the universe. Trying to comprehend or compare the size of BB(745) is just futile. Here [1] is a well known attempt to convey the size of 52!, the number of permutations of a deck of cards. [1] https://www.youtube.com/watch?v=ObiqJzfyACM&t=947s https://www.youtube.com/watch?v=ObiqJzfyACM&t=947s

explaininjs 3y ago
Right, but we are talking about the difference between two busy beavers here.
- danbruc 3y ago
  Sure, but BB(n) - BB(n - 1) ≈ BB(n) because the function grows so quickly that BB(n - 1) is essentially zero compared to BB(n). Even for factorials the difference between n! and (n - 1)! is essentially n! [1] and the busy beaver function grows much faster. BB(748) and BB(748) - BB(745) will have the same number of digits and if you compare them left to right, they will agree for way more digits than there are permutations of particles in the observable way before you find the first difference. [1] (1 - 1/n) n! to be precise.
  - explaininjs 3y ago
    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

explaininjs 3y ago

Right, but we are talking about the difference between two busy beavers here.

danbruc 3y ago
Sure, but BB(n) - BB(n - 1) ≈ BB(n) because the function grows so quickly that BB(n - 1) is essentially zero compared to BB(n). Even for factorials the difference between n! and (n - 1)! is essentially n! [1] and the busy beaver function grows much faster. BB(748) and BB(748) - BB(745) will have the same number of digits and if you compare them left to right, they will agree for way more digits than there are permutations of particles in the observable way before you find the first difference. [1] (1 - 1/n) n! to be precise.
- explaininjs 3y ago
  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