News for hackers. Stuff that matters.
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.