News for hackers. Stuff that matters.
Re:BB(3, 3) is Hard by nine_k on Tuesday October 17, 2023 @01:41AM (#37911045)
Computing BB(748) would be best, but if we could get an upper-bound estimate that's reasonably close, that would suffice.
Re:BB(3, 3) is Hard by meithecatte on Tuesday October 17, 2023 @02:18AM (#37911269)
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.
Re:BB(3, 3) is Hard by drpixie on Tuesday October 17, 2023 @02:02AM (#37911172)
Reaching a "reasonably close" upper bound estimate wouldn't provide proof ... probability maybe, but not proof.
Re:BB(3, 3) is Hard by dllthomas on Tuesday October 17, 2023 @02:29AM (#37911330)
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.
Re:BB(3, 3) is Hard by klempner on Tuesday October 17, 2023 @08:09AM (#37913720)
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.)