News for hackers. Stuff that matters.
Re:Why Busy Beaver hunters fear the Antihydra by shawnz on Monday October 27, 2025 @08:30PM (#45728022)
I think finding an upper bound is basically just as difficult as finding the actual value itself, since both would require proving that all of the programs which run longer than that will run forever. That's why we can say BB(x) grows faster than any computable function. Being able to compute BB(x) algorithmically or any faster growing function would let you solve the halting problem
Re:Why Busy Beaver hunters fear the Antihydra by throwaway81523 on Tuesday October 28, 2025 @02:08AM (#45729646)
Sure, but I only asked about the single case x=6.
Re:Why Busy Beaver hunters fear the Antihydra by thaumasiotes on Tuesday October 28, 2025 @06:32AM (#45731133)
If you want an unproven-but-almost-certainly-correct upper bound on BB(6), consider BB(12).
Re:Why Busy Beaver hunters fear the Antihydra by sligocki on Tuesday October 28, 2025 @04:46PM (#45738920)
Not sure if this is a joke, but actually that is guaranteed to be true. It is proven that for all n: BB(n+1) >= BB(n) + 3. But it is not proven that BB(n+1) >= BB(n) + 4, haha.
Re:Why Busy Beaver hunters fear the Antihydra by shawnz on Tuesday October 28, 2025 @08:48AM (#45732156)
The point stands: the hard part is proving that all the programs with longer runtime than your upper bound will never terminate, and once you've solved that, getting the exact value is just a little extra work
Re:Why Busy Beaver hunters fear the Antihydra by throwaway81523 on Thursday October 30, 2025 @06:07PM (#45765970)
For arbitrary n, that proof is arbitrarily hard, even undecidable for large enough n. Again though, for the specific case n=6, that difficulty has not yet been demonstrated, especially if you're willing to accept probabilistic arguments instead of rigorous proofs. n-by-n checkers is PSPACE-complete but the specific case n=8 that people actually play, has been completely solved using computers.