3 ms·

Sorry for a low quality/content comment, but this area has always seemed to me the most beautiful part of mathematics (not just theoretical computer science). T

Sorry for a low quality/content comment, but this area has always seemed to me the most beautiful part of mathematics (not just theoretical computer science). The joke about robot overlords still pondering on BB(<low double digit number>) billions of years into the future is a good summary of this feeling :)

v64 5y ago
Even calculating BB(30) exhaustively would require more energy than we have in the observable universe. The fact that functions like BB() have actual, finite values, but that they're unknowable both due to our physical and logical limitations, is humbling in an ineffable way.
- stouset 5y ago
  By physical limitations, we also include space. If you could represent each digit of Graham’s number (G_64) in a Planck volume, you couldn’t fit even an incomprehensibly tiny fraction of it in the observable universe. No only that, but the number of digits in G_64 (~log10(G_64)) exceeds the number of Planck volumes (V_p) in our universe too. As does the number of digits in that number (~log10^2(G_64)). And so on and so on, for a number of times itself exceeding the number of Planck volumes in the universe. P_v ~ 4.65e185 P_v < G_64 P_v < log10(G_64) P_v < log10^(2)(G_64) … P_v < log10^(P_v)(G_64) And yet G_64 < BB(18) We don’t yet know if it exceeds BB(17). That said, we can grow bigger still. Scott Aaron defined a closely-related concept called a Beeping Busy Beaver that grows uncomputably even if we had an oracle for BB(n). That is, even if we had access to a magic genie that could tell us any BB(n), this function BBB(n) even still grows uncomputably. It’s almost as if there’s “sizes” of uncomputability much the same as there are distinct sizes of infinity.
  - tromp 5y ago
    > We don’t yet know if it exceeds BB(17). We don't know if it exceeds BB(5) either, do we? In the functional realm [1], we know: BB_λ(36) < 5 * G_64 + 6 <= BB_λ(114) Note that these are measured in bits, and that it would take 18 * 2 * (2 + ceil(log(18))) = 252 bits to represent the 18-state TM computing G_64. The 847 state TM whose halting is known to be unprovable in ZFC takes 847 * 2 * (2 + ceil(log(847)) = 20328 bits to describe. Meanwhile, in a mere 215 bits, we can encode a Laver table program [2] whose halting is not known to be provable in ZFC [3]. I.e. it may or may not be unprovable, we don't know yet. [1] https://oeis.org/A333479 https://oeis.org/A333479 [2] https://github.com/tromp/AIT/blob/master/laver.lam https://github.com/tromp/AIT/blob/master/laver.lam [3] https://codegolf.stackexchange.com/questions/79620/laver-tab https://codegolf.stackexchange.com/questions/79620/laver-tab...
    - deleted 5y ago
      [deleted]
  - Sharlin 5y ago
    > It’s almost as if there’s “sizes” of uncomputability much the same as there are distinct sizes of infinity. There is, isn't there? A TM plus an oracle can solve the halting problem for the original TM but is just as susceptible to a halting problem of its own, and this goes on ad infinitum.
actually_a_dog 5y ago
This very much reminds me of the following story told by Joel Spencer regarding Ramsey numbers[0]: > Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens. [1] Although Ramsey numbers are computable, they are really, really hard to compute exactly, and we don't have great upper or lower bounds for them, either. Edit: I found the version of the story that I was more familiar with that had a 1 year time limit on it[2]: > Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack. --- [0]: https://en.wikipedia.org/wiki/Ramsey%27s_theorem https://en.wikipedia.org/wiki/Ramsey%27s_theorem [1]: https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Computational_complexity https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Computation... [2]: https://blogs.scientificamerican.com/roots-of-unity/moores-law-and-ramsey-numbers/ https://blogs.scientificamerican.com/roots-of-unity/moores-l...
galaxyLogic 5y ago
> The joke about robot overlords still pondering on BB This starts to sound like Hitchhiker's Guide to Galaxy. I always thought the answer 42 was just an absurd joke but now I'm starting to think that Douglas Adams must have known about Busy Beaver.
- perl4ever 5y ago
  The word on this, I believe, is: 'The first strong law of small numbers (Gardner 1980, Guy 1988, 1990) states "There aren't enough small numbers to meet the many demands made of them." The second strong law of small numbers (Guy 1990) states that "When two numbers look equal, it ain't necessarily so."' '...the first few values of the interpolating polynomial (n^4-6n^3+23n^2-18n+24)/24 (erroneously given in Guy (1990) with a coefficient 24 instead of 23) for n=1, 2, ... are 1, 2, 4, 8, 16, .... Thus, the polynomial appears to give the powers of 2, but then continues 31, 57, 99, ... (OEIS A000127). In fact, this sequence gives the maximal number of regions obtained by joining n points around a circle by chords' https://mathworld.wolfram.com/StrongLawofSmallNumbers.html https://mathworld.wolfram.com/StrongLawofSmallNumbers.html

v64 5y ago

Even calculating BB(30) exhaustively would require more energy than we have in the observable universe. The fact that functions like BB() have actual, finite values, but that they're unknowable both due to our physical and logical limitations, is humbling in an ineffable way.

stouset 5y ago
By physical limitations, we also include space. If you could represent each digit of Graham’s number (G_64) in a Planck volume, you couldn’t fit even an incomprehensibly tiny fraction of it in the observable universe. No only that, but the number of digits in G_64 (~log10(G_64)) exceeds the number of Planck volumes (V_p) in our universe too. As does the number of digits in that number (~log10^2(G_64)). And so on and so on, for a number of times itself exceeding the number of Planck volumes in the universe. P_v ~ 4.65e185 P_v < G_64 P_v < log10(G_64) P_v < log10^(2)(G_64) … P_v < log10^(P_v)(G_64) And yet G_64 < BB(18) We don’t yet know if it exceeds BB(17). That said, we can grow bigger still. Scott Aaron defined a closely-related concept called a Beeping Busy Beaver that grows uncomputably even if we had an oracle for BB(n). That is, even if we had access to a magic genie that could tell us any BB(n), this function BBB(n) even still grows uncomputably. It’s almost as if there’s “sizes” of uncomputability much the same as there are distinct sizes of infinity.
- tromp 5y ago
  > We don’t yet know if it exceeds BB(17). We don't know if it exceeds BB(5) either, do we? In the functional realm [1], we know: BB_λ(36) < 5 * G_64 + 6 <= BB_λ(114) Note that these are measured in bits, and that it would take 18 * 2 * (2 + ceil(log(18))) = 252 bits to represent the 18-state TM computing G_64. The 847 state TM whose halting is known to be unprovable in ZFC takes 847 * 2 * (2 + ceil(log(847)) = 20328 bits to describe. Meanwhile, in a mere 215 bits, we can encode a Laver table program [2] whose halting is not known to be provable in ZFC [3]. I.e. it may or may not be unprovable, we don't know yet. [1] https://oeis.org/A333479 https://oeis.org/A333479 [2] https://github.com/tromp/AIT/blob/master/laver.lam https://github.com/tromp/AIT/blob/master/laver.lam [3] https://codegolf.stackexchange.com/questions/79620/laver-tab https://codegolf.stackexchange.com/questions/79620/laver-tab...
  - deleted 5y ago
    [deleted]
- Sharlin 5y ago
  > It’s almost as if there’s “sizes” of uncomputability much the same as there are distinct sizes of infinity. There is, isn't there? A TM plus an oracle can solve the halting problem for the original TM but is just as susceptible to a halting problem of its own, and this goes on ad infinitum.

actually_a_dog 5y ago

This very much reminds me of the following story told by Joel Spencer regarding Ramsey numbers[0]: > Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens. [1] Although Ramsey numbers are computable, they are really, really hard to compute exactly, and we don't have great upper or lower bounds for them, either. Edit: I found the version of the story that I was more familiar with that had a 1 year time limit on it[2]: > Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack. --- [0]: https://en.wikipedia.org/wiki/Ramsey%27s_theorem https://en.wikipedia.org/wiki/Ramsey%27s_theorem [1]: https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Computational_complexity https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Computation... [2]: https://blogs.scientificamerican.com/roots-of-unity/moores-law-and-ramsey-numbers/ https://blogs.scientificamerican.com/roots-of-unity/moores-l...

galaxyLogic 5y ago

> The joke about robot overlords still pondering on BB This starts to sound like Hitchhiker's Guide to Galaxy. I always thought the answer 42 was just an absurd joke but now I'm starting to think that Douglas Adams must have known about Busy Beaver.

perl4ever 5y ago
The word on this, I believe, is: 'The first strong law of small numbers (Gardner 1980, Guy 1988, 1990) states "There aren't enough small numbers to meet the many demands made of them." The second strong law of small numbers (Guy 1990) states that "When two numbers look equal, it ain't necessarily so."' '...the first few values of the interpolating polynomial (n^4-6n^3+23n^2-18n+24)/24 (erroneously given in Guy (1990) with a coefficient 24 instead of 23) for n=1, 2, ... are 1, 2, 4, 8, 16, .... Thus, the polynomial appears to give the powers of 2, but then continues 31, 57, 99, ... (OEIS A000127). In fact, this sequence gives the maximal number of regions obtained by joining n points around a circle by chords' https://mathworld.wolfram.com/StrongLawofSmallNumbers.html https://mathworld.wolfram.com/StrongLawofSmallNumbers.html