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.
[ Parent
| on HN ]
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.