Comment by bo1024
8 months ago
I think the more correct statement is that there are different models of ZFC in which BB(748) are different numbers. People find that weird because they don't think about non-standard models, as arguably they shouldn't.
How is that possible? That implies there’s at least one specific program whose execution changes based on the ZFC model. The rules of program execution are so simple, it doesn’t make sense that they’d change based on anything like that.
Because what it means to "halt in finite time" has different meanings in different models, because time is measured with different numbers.
I don’t get it. Let’s say that BB(748) is 10,000. (I realize the true number is somewhat larger, this is just an example that doesn’t change the argument.) That means there’s one or more Turing machines of that size which run for that many steps. All of the others either run for fewer, or never stop.
Running for fewer steps is extremely well defined and I don’t imagine that enters into this.
That means there’s issue is “never stop”? That also seems pretty well defined to me. For BB(748) to vary based on your model, if the machines that run for fewer steps don’t change, then that means one of the machines that never stops in one model will stop in another. Or the BB winner for our model will never stop in another model.
How can changing your model make it so a specific Turing machine goes from stopping after 10,000 steps to never stopping, or from never stopping to stopping after 11,000 steps?
37 replies →
Isn't that incompatible with the models being consistent?
Suppose model A proves BB(748) = X and model B proves BB(748) = Y > X. But presumably the models can interpret running all size 748 Turing machines for Y steps. Either one of the machines halts at step Y (forming a proof within A that BB(748) >= Y contradicting the assumed proof within A that BB(748) = X < Y) or none of the machines halts at step Y (forming a proof within B that BB(748) != Y contradicting the assumed proof within B that BB(748) = Y).
I'm guessing the only way this could ever work would be some kind of nastiness like X and Y aren't nailed down integers, so you can't tell if you've reached them or not, and somehow also there's a proof they aren't equal.
The issue is that X and Y are not actual natural numbers. They are mathematical objects that satisfy all the ZFC axioms and Peano arithmetic but are infinitely large. The issue is that ZFC underspecifies natural numbers.