4 ms·

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 va

by 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.

by v64 5y ago

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.