3 ms·
Infinitary in the sense that a proof of non-halting must be strong enough to establish something about all natural numbers (does not halt after 1 step, does not
by karatinversion 4y ago
Infinitary in the sense that a proof of non-halting must be strong enough to establish something about all natural numbers (does not halt after 1 step, does not halt after 2 steps, does not halt after 3 steps…) which cannot be done on a case-by-case (“finitary”) way. In contrast to a proof of halting, which can be so done.
- nickdrozd 4y agoThe usual way to deal with an infinite number of cases is to group them into a finite number of cases and then deal with those. That's how induction works. So if you can prove that (1) the machine is in a certain condition at some step and (2) whenever the machine is in that condition at some step it will get back into that same condition at a later step, then you can prove that the machine will never halt.
- samatman 4y agoRight, the act of iterating a cycle might be infinite but the cycle itself is finite. Proving that nothing can break the cycle is possible in many simple cases.