4 ms·

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 t

by bo1024 1y 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.

deleted 1y ago
[deleted]
Strilanc 1y ago
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.
- Kranar 1y ago
  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.
wat10000 1y ago
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.
- bo1024 1y ago
  Because what it means to "halt in finite time" has different meanings in different models, because time is measured with different numbers.
  - wat10000 1y ago
    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?
    - Kranar 1y ago
      Yes the issue has to do with "never stops". One of the machines that never stops in one model will stop in another model. So in one model a Turing Machine called R never stops. In another model R stops after Q steps. But here's the issue... Q isn't an actual natural number, what it is is some mathematical object that satisfies all of the properties of a natural number in ZFC, but is not an actual natural number. What it actually is is some infinitely large object that satisfies all of the Peano axioms of what a natural number is as well as satisfies the following set of rules: Q > 0 Q > 1 Q > 2 Q > 3 ... Q is basically some infinitely large construct that from within the model appears to be finite, but from outside of the model is not finite. So within this model, the Turing machine R halts after Q steps, and since from within the model Q is finite then from within this model BB(748) is at least equal to Q. If BB(748) is actually 10,000, then we can add this as an axiom to ZFC to get a new formal theory ZFC + "BB(748) = 10000". In this new theory the previous structure that contained Q as an element will not satisfy the definition of a natural number, so we don't have to worry about Q anymore... however, there will exist some number T > 748 where BB(T) is independent of our new theory. For BB(T), there will exist some other model that has its own Q* which satisfies all of our axioms including the axiom that BB(748) = 10000, but also that Q* > 0 Q* > 1 Q* > 2 Q* > 3 ... And rinse and repeat...

by bo1024 1y ago

deleted 1y ago

[deleted]

Strilanc 1y ago

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.

Kranar 1y ago
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.

wat10000 1y ago

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.

bo1024 1y ago
Because what it means to "halt in finite time" has different meanings in different models, because time is measured with different numbers.
- wat10000 1y ago
  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?
  - Kranar 1y ago
    Yes the issue has to do with "never stops". One of the machines that never stops in one model will stop in another model. So in one model a Turing Machine called R never stops. In another model R stops after Q steps. But here's the issue... Q isn't an actual natural number, what it is is some mathematical object that satisfies all of the properties of a natural number in ZFC, but is not an actual natural number. What it actually is is some infinitely large object that satisfies all of the Peano axioms of what a natural number is as well as satisfies the following set of rules: Q > 0 Q > 1 Q > 2 Q > 3 ... Q is basically some infinitely large construct that from within the model appears to be finite, but from outside of the model is not finite. So within this model, the Turing machine R halts after Q steps, and since from within the model Q is finite then from within this model BB(748) is at least equal to Q. If BB(748) is actually 10,000, then we can add this as an axiom to ZFC to get a new formal theory ZFC + "BB(748) = 10000". In this new theory the previous structure that contained Q as an element will not satisfy the definition of a natural number, so we don't have to worry about Q anymore... however, there will exist some number T > 748 where BB(T) is independent of our new theory. For BB(T), there will exist some other model that has its own Q* which satisfies all of our axioms including the axiom that BB(748) = 10000, but also that Q* > 0 Q* > 1 Q* > 2 Q* > 3 ... And rinse and repeat...