3 ms·
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 whic
by shawnz 11mo ago
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
- throwaway81523 11mo agoSure, but I only asked about the single case x=6.
- thaumasiotes 11mo agoIf you want an unproven-but-almost-certainly-correct upper bound on BB(6), consider BB(12).
- sligocki 11mo agoNot 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.
- shawnz 11mo agoThe 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
- throwaway81523 11mo agoFor 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.