4 ms·
>whether that specific machine halts still has a deterministic, well-defined answer Really? If there is literally no procedure that can tell the difference be
by isotropy 10y ago
>whether that specific machine halts still has a deterministic, well-defined answer
Really? If there is literally no procedure that can tell the difference between "machines that will never halt" and "machines that will run longer than you can afford to wait", you're basically calling for a concept of "deterministic" where it's ok if a final determination never happens, and in some cases (which you can't identify), can't happen. That seems like it's counter to the spirit of calling something deterministic.
- naasking 10y agoJust because there's no general algorithm to determine whether Turing machine X may halt, does not preclude the existence of specific Turing machines that can determine whether X will halt. This is part of the difference between truth and proof. Whether X will halt is true or false regardless of whether to use can prove it to be true or false in any given logic.