3 ms·
Yes - this is true. A program will either halt or not, and if you could pluck that answer from somewhere, you would know. But my point is in practice, this is
by swid 5y ago
Yes - this is true. A program will either halt or not, and if you could pluck that answer from somewhere, you would know.
But my point is in practice, this is just not possible, because the problem spaces are too large.
A related problem is the Busy Beaver Problem - how many steps can a program take as a factor of the number of turing instructions it contains. If we could determine that, we would "solve" the halting problem, in that we would know a program that is still running after N steps will never terminate.
However, even for very small programs, N is so large to be incomprehensible; ie, all the stars will have burned out even with all the compute in the world running until that happens.
- anyfoo 5y agoAnd 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.