Hacker News new | ask | show | jobs
by Hercuros 1464 days 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.

1 comments

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!