Re:How the Slowest Computer Programs Illuminate Math’s Funda...
by tromp on Friday December 11, 2020 @11:14AM
(#25387366)
Yes, 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).
Re:How the Slowest Computer Programs Illuminate Math’s Funda...
by ifdefdebug on Friday December 11, 2020 @05:05PM
(#25391896)
Thanks again, I can see now how my question was nonsensical...
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.