3 ms·
No, 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
by belovedeagle 13y ago
No, 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.