4 ms·

> there is nothing in principle stopping us from running this machine for BB(748) steps How would we compute the value of BB(748)?

• 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 ago
    Reaching a "reasonably close" upper bound estimate wouldn't provide proof ... probability maybe, but not proof.
    • dllthomas 3y ago
      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.
  • meithecatte 3y ago
    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 3y ago
    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.)