5 ms·
Computing BB(748) would be best, but if we could get an upper-bound estimate that's reasonably close, that would suffice.
by nine_k 3y ago
Computing BB(748) would be best, but if we could get an upper-bound estimate that's reasonably close, that would suffice.
- drpixie 3y agoReaching a "reasonably close" upper bound estimate wouldn't provide proof ... probability maybe, but not proof.
- dllthomas 3y agoIf we've proved that a number is an upper bound on BB(748), then running for that many steps without halting means it has also run BB(748) steps without halting.
- meithecatte 3y agoDo note that any function f(n) that is always (or even just eventually always) greater than BB(n), is uncomputable, for very similar reasons.
- klempner 3y agoHow can you come up with an "upper bound estimate" without having some idea of the structure of the computation of the specific 748 state Turing Machine in question? Imagine you had an oracle telling you BB(748) excluding this machine. How do you get an upper bound on the runtime of this machine? (There is an answer: this is surely not the optimal construction, and so such an oracle would give you an answer for some smaller ZFC machine which you could likely use to extrapolate a value for this machine. However, eventually you'll find a minimal state ZFC machine and that won't work anymore.)