Even simpler, you're just trying to figure out if it halts or not, not the exact length of the cycle, so you can do it with only a single counter for the total

Even simpler, you're just trying to figure out if it halts or not, not the exact length of the cycle, so you can do it with only a single counter for the total number of states. Say you have a machine with 128 bits of state, if it halts in 2^128 (roughly 340 undecillion) steps, that means it halts. If it's still going after 2^128 steps, then it'll keep going forever. So, to see if a 128 bit machine halts, you only need an extra 128 bits to count up 1-by-1 to 2^128. Sure, you also need a few thousand times the lifetime of the known universe just to count that high, but you know, It's O(2^128) instructions which means it's O(1). Good luck doing that on any machine with any real amount of memory of course. Really easy to write "just count to 2^128", but not so easy to do it.