You can model the state transitions as a linked list and use Floyd's classical tortoise and hare algorithm to (eventually) determine a cycle exists. Initialize "tortoise" and "hare" as two copies of initial state and advance hare by two instructions and tortoise by one each iteration. A cycle is reported if the two states become equal again.
A cycle of n instructions starting at instruction n0 will be detected in between n0 and n0+n iterations (i.e. <= 3*(n0+n) underlying instructions) since n0 iterations gets both into the cycle and the offset between them will become 0 some time in the next n iterations.
n could be very large, of course (e.g, using all of memory as a giant counter so the cycle length is huge), but the cycle detection is not really making your problem worse.
In this case, I'll back it down to suggesting there's probably some way to prove it can't be done without some unreasonable amount of at least one of time and space.