Re:Latest Busy Beaver champion has too many digits to count
by dash2 on Wednesday June 22, 2022 @09:49AM
(#31835946)
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"?)
[ Parent
| on HN ]
Re:Latest Busy Beaver champion has too many digits to count
by cwillu on Wednesday June 22, 2022 @10:49AM
(#31836731)
Kinda, yes, although the implication is typically taken the opposite direction. There are busy beavers who's halting cannot be proven in ZFC!
Re:Latest Busy Beaver champion has too many digits to count
by sligocki on Wednesday June 22, 2022 @11:06AM
(#31836985)
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!
Re:Latest Busy Beaver champion has too many digits to count
by kevinventullo on Wednesday June 22, 2022 @10:50AM
(#31836738)
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.
Re:Latest Busy Beaver champion has too many digits to count
by ravi-delia on Wednesday June 22, 2022 @01:38PM
(#31839206)
Try trillions of trillions, but at the end you've proven everything! Even less useful, but significantly weirder.