5 ms·
One of the curiosities about this function is that computing BB(748) is independent of ZFC. https://scottaaronson.blog/?p=4916 https://scottaaronson.blog/?p=49
by henry2023 1y ago
One of the curiosities about this function is that computing BB(748) is independent of ZFC.
https://scottaaronson.blog/?p=4916 https://scottaaronson.blog/?p=4916
- Sniffnoy 1y agoThe record's been lowered since then, I should note. At least down into the 600s, I've seen claims of down in the 400s. But I haven't really kept up with this.
- red75prime 1y agoIn other words, Turing machine creates mathematical reality, which is independent from our assumptions.
- cwillu 1y agoNo, that's a misconception. If you add BB(748)==‹any N but the correct number›, you get an inconsistent system that will either claim that a machine doesn't halt even though it does (e.g. the real BB champion), or that some machine does halt at N steps, which you can then disprove by enumerating all the turing machines of the relevant number of states for N steps, and showing that no machine halts at that step. Either way, the only BB axiom you can add without blowing up ZFC is the correct one.
- emtel 1y agoNope, that’s the crazy thing. busy beaver numbers are simple arithmetical constructions. There is a fact of the matter about each value of BB(n)! We just can’t ever know more than a small handful of them.