4 ms·
> But then this program does not halt, since its halting would mean that ZFC can prove that this program halts. That step is not logically consistent. It could
by SAI_Peregrinus 3y ago
> But then this program does not halt, since its halting would mean that ZFC can prove that this program halts.
That step is not logically consistent. It could halt, it's just that ZFC can't prove it will ever do so. For example, the program which computes the 8000th busy beaver number halts (per definition of the busy beaver function), but is undecidable in ZFC[1].
An undecidable program can halt. An undecidable program can run forever. But whatever axiom system is being used to decide that can't prove which (without running the program, potentially for an infinite number of steps).
[1] https://scottaaronson.blog/?p=2725 https://scottaaronson.blog/?p=2725
- deleted 3y ago[deleted]
- bmacho 3y ago> For example, the program which computes the 8000th busy beaver number I don't believe that there exist such a program.
- SAI_Peregrinus 3y agoWhy not? That implies that an 8000 state Turing machine which eventually halts when started with a blank tape doesn't exist. If any of them do (and it's trivial to simulate one), then exactly such a program can exist.
- bmacho 3y agoWell, there can indeed exist a program that writes out the number BB(8000). (In the sense that it is consistent with ZFC that there is a program that writes out the number of steps of the smallest contradiction in ZFC.) What I don't believe that there exist a program that is a proper counter-example, that is, its halting is undecidable in ZFC, and it halts. Exactly because what I wrote earlier.