3 ms·
And my point is that in general it’s not even possible in theory. You brought an example for something where a particular instance is practically unsolvable (b
by anyfoo 5y ago
And my point is that in general it’s not even possible in theory.
You brought an example for something where a particular instance is practically unsolvable (because you will run out of time). But it’s still possible to formulate an easy criterium for halting for that program, as I did above.
There are however programs where you can’t know if it halts or not for any input. No criteria can be made (apart from semi-decidable ones: “I know it doesn’t halt for x, does halt for y, but I still don’t know about z”). There is nothing where you can pluck the answer from, as you put it.
- swid 5y agoI’m pretty sure that isn’t true for real programs. The computer has a finite number of possible states depending on its physical properties or theoretical architecture - if you return to a state, there is a cycle and it will not terminate. Eventually it will hit the cycle or terminate.