4 ms·

It's hard to comprehend just how big that number is. It may indeed be among the largest numbers ever conceived, and we'd have no clue. I wouldn't be surprised i

It's hard to comprehend just how big that number is. It may indeed be among the largest numbers ever conceived, and we'd have no clue. I wouldn't be surprised if it is larger the number of possible permutations of all particles in the observable universe, for instance. I'd be more surprised if it was less than that.

MichaelDickens 3y ago
Graham's number used to be the largest number ever used in a proof, but BB(745) is much larger—Graham's number has been proven to be smaller than BB(16)[1] (although I don't know how carefully the proof has been checked). [1] https://www.sligocki.com/2022/07/11/bb-16-graham.html https://www.sligocki.com/2022/07/11/bb-16-graham.html
- tromp 3y ago
  A number much larger than Graham's can be represented in less than 64 bits [1], using a functional flavored Busy Beaver function [2]. [1] https://googology.fandom.com/wiki/User_blog:JohnTromp/The_largest_number_representable_in_64_bits https://googology.fandom.com/wiki/User_blog:JohnTromp/The_la... [2] https://oeis.org/A333479 https://oeis.org/A333479
danbruc 3y ago
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.

MichaelDickens 3y ago

Graham's number used to be the largest number ever used in a proof, but BB(745) is much larger—Graham's number has been proven to be smaller than BB(16)[1] (although I don't know how carefully the proof has been checked). [1] https://www.sligocki.com/2022/07/11/bb-16-graham.html https://www.sligocki.com/2022/07/11/bb-16-graham.html

tromp 3y ago
A number much larger than Graham's can be represented in less than 64 bits [1], using a functional flavored Busy Beaver function [2]. [1] https://googology.fandom.com/wiki/User_blog:JohnTromp/The_largest_number_representable_in_64_bits https://googology.fandom.com/wiki/User_blog:JohnTromp/The_la... [2] https://oeis.org/A333479 https://oeis.org/A333479

danbruc 3y ago

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.