You run the program for 2^(bits of state) steps. If it's still running, it will never stop because it must have repeated a state at least once. That means it's in a loop. So it takes a long time, but not an uncomputably long time.

By bits of state, I only mean the bits that the program is allowed to change. It doesn't necessarily include OS code or initialization code, as long as they are immutable while the program is running.

Ah, yep, you're right.

Finite state -> solved halting problem