On: BB(3, 3) is Hard

[nine_k]

Computing BB(748) would be best, but if we could get an upper-bound estimate that's reasonably close, that would suffice.

[meithecatte → nine_k]

Do 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 → nine_k]

How 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.)

[drpixie → nine_k]

Reaching a "reasonably close" upper bound estimate wouldn't provide proof ... probability maybe, but not proof.

[dllthomas → drpixie]

If 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.