3 ms·
The approach would be to fix an upper bound on memory and to enumerate all possible state, running the program each time and determining if all cases terminate
by just2n 13y ago
The approach would be to fix an upper bound on memory and to enumerate all possible state, running the program each time and determining if all cases terminate or if any runs forever?
I think the real crux of the problem is that you can't determine in any of those cases whether the program is going to terminate. Consider bogosort or a brute-force algorithm for solving travelling salesman. These can take millions of years to complete even for small input sizes. Do we consider that an "infinite" runtime?
- belovedeagle 13y agoNo, the algorithm is to run the program and see if any state is repeated; if it is, the program is in an infinite loop (where "state" means, roughly, all memory and remaining length of input). Of course, this requires 2^[bits of state] bits of memory, and a similar amount of time. Obviously an interesting (read: approximate) solver would use tighter heuristics.
- sp332 13y agoConsider bogosort That's true, external inputs and true randomness is not accounted for. (However pseudorandom generators are included!)