Comment by wat10000
8 months ago
> ZFC doesn't prevent us from defining a non-standard model where Bar halts after a non-standard number of steps.
But it does prevent you from defining a non-standard model where Bar halts after a finite number of steps. Since BB is finite by definition, the non-standard number of steps after which Bar halts cannot be BB(748).
I’m pretty sure you and the other commenter have this mixed up. The fact that BB(748) is independent of ZFC doesn’t mean there are different models that have different values of BB(748). It means that ZFC is insufficient to determine the value of BB(748). That value is still some finite integer, you just can’t prove which one it is. Equivalently, there is some 748-state Turing machine which never halts but ZFC cannot prove never halts.
And no, you can’t change your model such that this Turing machine halts in some non-standard number of steps. Or rather, you can, but that doesn’t actually change anything. The machine still doesn’t halt for the purposes of defining BB(748).
> I’m pretty sure you and the other commenter have this mixed up.
We really don't.
> that BB(748) is independent of ZFC
> there are different models that have different values of BB(748)
> ZFC is insufficient to determine the value of BB(748)
These three statements are equivalent.
f(n)=X is independent of ZFC means there are different models of ZFC that have different values of f(n). It's a very trivial theorem[0]. If you don't like it, I can't convince you otherwise.
> that doesn’t actually change anything
Changing the model will not change how any machine works in our physical, mechanical universe. However, it does change the value of BB(748).
I understand your line of thinking: There is only one mechanical universe, which is the one where we exist. We can build Turing machines in this universe. BB(n) depends on Turning machines. Since there is only one single universe, there is only one single value of BB(n).
It's a perfectly fine mental model for most cases. This was exactly how I thought when the first time I heard about BB(n). But it's not the kind of math than Scott Aaronson et al. are doing.
Bar keeps running in our mechanical universe. But it can also halt in some non-standard number of steps. This weird, absurd-sounding proposition works because non-standard numbers simply don't map to anything in mechanical universe. They're purely abstract objects living in ZFC+~Con(ZFC).
[0]: Given f(n)=X is independent of ZFC. Which means f(n)=X and ~(f(n)=X) are both consistent relative to ZFC. Therefore, if there is any model of ZFC, there is a model M1 that entails ZFC+(f(n)=X), and a model M2 that entails ZFC+~(f(n)=X). The value of f(n) cannot be the same in M1 and M2.
My argument has nothing to do with the universe. My argument is that there is a single definition of the BB function and its definition does not allow for different values in different circumstances.
What is “a model” here? Can I say that there’s a model ZFC’ which is the same as ZFC except that 107 is considered to be equivalent to 200, and therefore BB(4) in ZFC’ is actually 200? Or can I say that ZFC’’ says integers only go up to 100 and therefore BB(4) is 100 in that model? Or is it something more restricted than that?
> Or can I say that ZFC’’ says integers only go up to 100 and therefore BB(4) is 100 in that model?
You'd be defining a new axiomatic system here, not just a model of ZFC. I don't know how we're going to formalize Turning machine in this system, but if we managed to do it, the value of BB(4) is likely to be indeed 100, at least for some models of this new system.
Roughly speaking, a model of ZFC is a set and a binary relationship over the set, whose members all satisfy every axiom of ZFC. Obviously this super simplified definition does a crazy amount of handwaving.
But we don't need to accept or understand the idea of model. What we need to accept is this simple idea:
An axiomatic system can be consistent, but wrong.
For example, if ZFC is consistent, then T = ZFC+~Con(ZFC) would be consistent as well. But this T is wrong, as it believes ZFC is inconsistent.
Similarly, if ZFC is indeed consistent, then T is wrong about which Turing machines halt. Therefore it would have a wrong value of BB(748) (and many other BB(n)).
However, since ZFC can't prove its own consistency, it can't prove that value is wrong. That's why there are different values of BB(748). Those values are not necessarily equally correct, it's just that ZFC isn't strong enough to prove which one is wrong.
Models, nonstandard natural numbers, etc... are more or less technical details (so mathematicians can avoid scary terms like 'wrong'.)
20 replies →