3 ms·
So does this mean that "the machine that halts if ZF is inconsistent" is guaranteed to not halt (and not loop) in less than BB(748) steps? Or would it be possi
by ifdefdebug 6y ago
So does this mean that "the machine that halts if ZF is inconsistent" is guaranteed to not halt (and not loop) in less than BB(748) steps?
Or would it be possible for some crazy billionaire to throw immensurable amounts of computing power at the problem and run the machine just to, after a few years, wake up one morning, find that his machine has halted, and tell the world he had proved ZFC to be inconsistent?
Likewise, could he wake up one morning, find his machine caught in an infinite loop, and tell the world "hey, I just proved this machine will never halt, so I proved ZF to be consistent, quod est adsurdum so better forget about ZFC...
- tromp 6y agoA machine looking for inconsistencies cannot enter an infinite loop. The belief that ZFC is consistent is as good as a guarantee that this machine will never halt. It will endlessly search for a non-existing proof of inconsistency. Btw, even an attempted computation of BB(10) will outlast the heat death of the universe.
- ifdefdebug 6y agoThanks for your answer. But I think this does not address my question (I am genuinely curious from a layman's point of view). As far as I understood from the article: A well known TM exists with 748 rules, that halts if ZF is inconsistent. Anybody can build and run that machine. Is that correct? If that is correct, I can run that machine. Imagine I have loads of computing power to run it. Do I have a chance, in principle, even if it is an infinitesimal chance, to either step into a loop or see my machine halting, before BB(748) steps have been done, maybe even within my own lifetime (in principle)? Or is it guaranteed that this machine can not loop or halt before BB(748) steps? I think it is an interesting question, because in the first case, a proof of ZFC inconsistency would be possible in principle if I get lucky and a halt or loop exists early on (though a proof of consistency would not), in the latter case it would not be possible even in principle because of the limitations of our universe.
- deleted 6y ago[deleted]
- tromp 6y agoYes, you can run the machine that looks for ZFC inconsistencies. And if it halts, it is necessarily within BB(748) steps, as that forms an upper bound on the halting time of any 748 rule TM. Just know that BB(748) is incomprehensibly larger than BB(10) and the latter can't even be computed within the lifetime of the universe. But yes, in principle you could stumble upon a ZFC inconsistency that can be proved very easily and takes much fewer steps than even BB(10).
- ifdefdebug 6y agoThanks again, I can see now how my question was nonsensical...