3 ms·

With BB it's not so surprising that it's weird because if it weren't, you could cheat! Say you know that a Turing machine which computers digits of the goldbach

With BB it's not so surprising that it's weird because if it weren't, you could cheat! Say you know that a Turing machine which computers digits of the goldbach conjecture has n states. Then if you could just get BB(n), or even if BB(n) is too predictable, you could just run that Turing machine for over BB(n) steps and know it doesn't halt. So we can informally see that BB will necessarily be at least as hard as all of math. Nature abhors a vacuum, but math abhors a shortcut. Every time we find one, it turns out to be deeper and more beautiful than expected.

Hercuros 4y ago
To be fair, even if you were able to get BB(n), it might still be (and probably is) some ridiculously large number, like a billion times the number of atoms in the universe or something. So that wouldn't really help you solve any math problems even if you were able to get the maximum amount of steps For a lot of things, like solving boolean SAT, we have the equivalent of a "busy-beaver" limit: if you want to solve a SAT instance of size n, you need at most 2^n steps. And being able to solve arbitrary SAT instances in reasonable time would be huge for mathematical proofs as well, because you could do stuff like find proofs up to a fixed size quickly. Point is that math is probably even harder than BB in some sense, since having BB would not really help you solve math problems in practice most likely.
- ravi-delia 4y ago
  Oh absolutely, you could never actually use BB(n) even with an oracle on hand. I simplify to cheating on math mostly because it's sort of crazy to think about coming at a problem from that angle (if the Goldbach conjecture is false there's obviously some N where it stops holding, but it's bizarre that you can formulate an N which is independent of the question), but really BB is hard because it's such a slight relaxation of the halting problem. It is a little more interesting (to me at least) than SAT because you expect SAT to be as hard as math. I mean, it's basically just a proof done the long hard way. But even though BB(n) doesn't provide an especially useful upper bound, it does let you expand the halting problem out large enough to use as a bludgeon, since even having information about BB(n) would still let you cheat. It's fun that way!
dash2 4y ago
Stupid question: does this imply that busy beaver machines might eventually tell us things about the rest of maths (like are there any real functions that you could say "ah the relevant machine runs for at least BB(n) steps and so we have proved X for infinity"?)
- cwillu 4y ago
  Kinda, yes, although the implication is typically taken the opposite direction. There are busy beavers who's halting cannot be proven in ZFC! https://scottaaronson.blog/?p=2725 https://scottaaronson.blog/?p=2725
- kevinventullo 4y ago
  I think the practicality of this approach is analogous to iterating through all possible proofs that are less than a million pages, checking each to see if they are a valid proof of the Riemann Hypothesis.
  - ravi-delia 4y ago
    Try trillions of trillions, but at the end you've proven everything! Even less useful, but significantly weirder.
- sligocki 4y ago
  It's a good question. Yes and no. If the "God of Busy Beaver" told us a value of BB(n) (for large enough n) then that would reduce some math problems to "simply" running a TM for that many steps and seeing if it halted. However, there are (at least) two issues with this: (1) As we can see, the number of steps will be unbelievably large (even just for 6-states, 2-symbols!), so it won't really be practical to run a TM that long and (2) The only known way to prove BB(n) numbers is by directly proving the halting / non-halting of every single TM of that size ... so, in other words, we will not know BB(n) until we have already proven all the interesting math that can be encoded in n-state TMs!

Hercuros 4y ago

To be fair, even if you were able to get BB(n), it might still be (and probably is) some ridiculously large number, like a billion times the number of atoms in the universe or something. So that wouldn't really help you solve any math problems even if you were able to get the maximum amount of steps For a lot of things, like solving boolean SAT, we have the equivalent of a "busy-beaver" limit: if you want to solve a SAT instance of size n, you need at most 2^n steps. And being able to solve arbitrary SAT instances in reasonable time would be huge for mathematical proofs as well, because you could do stuff like find proofs up to a fixed size quickly. Point is that math is probably even harder than BB in some sense, since having BB would not really help you solve math problems in practice most likely.

ravi-delia 4y ago
Oh absolutely, you could never actually use BB(n) even with an oracle on hand. I simplify to cheating on math mostly because it's sort of crazy to think about coming at a problem from that angle (if the Goldbach conjecture is false there's obviously some N where it stops holding, but it's bizarre that you can formulate an N which is independent of the question), but really BB is hard because it's such a slight relaxation of the halting problem. It is a little more interesting (to me at least) than SAT because you expect SAT to be as hard as math. I mean, it's basically just a proof done the long hard way. But even though BB(n) doesn't provide an especially useful upper bound, it does let you expand the halting problem out large enough to use as a bludgeon, since even having information about BB(n) would still let you cheat. It's fun that way!

dash2 4y ago

Stupid question: does this imply that busy beaver machines might eventually tell us things about the rest of maths (like are there any real functions that you could say "ah the relevant machine runs for at least BB(n) steps and so we have proved X for infinity"?)

cwillu 4y ago
Kinda, yes, although the implication is typically taken the opposite direction. There are busy beavers who's halting cannot be proven in ZFC! https://scottaaronson.blog/?p=2725 https://scottaaronson.blog/?p=2725
kevinventullo 4y ago
I think the practicality of this approach is analogous to iterating through all possible proofs that are less than a million pages, checking each to see if they are a valid proof of the Riemann Hypothesis.
- ravi-delia 4y ago
  Try trillions of trillions, but at the end you've proven everything! Even less useful, but significantly weirder.
sligocki 4y ago
It's a good question. Yes and no. If the "God of Busy Beaver" told us a value of BB(n) (for large enough n) then that would reduce some math problems to "simply" running a TM for that many steps and seeing if it halted. However, there are (at least) two issues with this: (1) As we can see, the number of steps will be unbelievably large (even just for 6-states, 2-symbols!), so it won't really be practical to run a TM that long and (2) The only known way to prove BB(n) numbers is by directly proving the halting / non-halting of every single TM of that size ... so, in other words, we will not know BB(n) until we have already proven all the interesting math that can be encoded in n-state TMs!