4 ms·
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 c
by 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 agoKinda, 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 agoI 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 agoTry trillions of trillions, but at the end you've proven everything! Even less useful, but significantly weirder.
- sligocki 4y agoIt'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!