Just as I was going to suggest <PERSON>'s cycle-detection algorithm, <PERSON>'s post beat me to it. However, the whole thing can be made more practical by speeding up comparisons of full states.
The bottleneck of the proposed algorithm would be in comparing full state. These comparisons will usually not finish, but stop early --- at the first difference. One optimization is to remember where the past differences occurred, and check those parts of the state first. For example, maintain a list of locations, and go through this list before making a full comparison. When a location from this list exposes a difference, stop the comparison (with failure), and move the location to the front of the list.
A different (and potentially more scalable) approach is to use incremental hashing. Pick a function of the full state such that the hash values are easy to adjust in O(1) when some part of the state changes. 125
For example, take a weighted sum of state words mod some large prime and concatenate with the unweighted sum mod some other large prime (can also throw in a modular weighted sum of squares of words, with different weight and modulus). This way, hash updates will take O(1) time on each execution step, and comparisons will take O(1) time until you get a hit. The probability of a false positive (i.e., the hashes match while the states differ) is very low, and even if this ever happens, it will amortize over a large number of true negatives (false negatives are impossible).
Of course, in practice, it seems more likely to get into situations like generating digits of the number pi --- things keep on changing, but never end. Another frequent possibility is that the infinite loop allocates memory, in which case it quickly exhausts all available memory.
In my course on algorithms and data structures, our autograder has to deal with student submissions that sometimes get into infinite loops. This is taken care of by a 30-second time-out and a certain memory limit. Both are much looser than runtime and memory budgets we impose as part of grading. I am not sure if implementing true infinite-loop detection would make a lot of sense in this context because such programs will run quite a bit slower (this is where hardware support for state hashing could help, but again you'd need additional uses to justify this). When students know that their program timed out, they can usually find the infinite loop. 125