You wouldn't necessarily need to keep track of all states that have been visited before, to my understanding, just one extra state that you move along at half the speed (so it'll eventually also enter the loop, and then the state you're progressing at full speed will loop around and hit it). So 2X the memory and 1.5X the time/compute of the program on its own.

▲

Tainnor 6 months ago | parent | next [-]

This is interesting and I wasn't aware of this algorithm, thanks.

I still maintain that it's practically infeasible to exhaust the entire state space of any modern machine.

	▲	Ukv 6 months ago \| parent [-]
		True, but practically I don't think you'd ever need to - should be able to narrow things down with insights/heuristics (and even with the simple algorithm alone, most programs would loop or halt far sooner). Often seems to be presented as if humans can make some deductions or introspections that machines/AI would be incapable of seeing, or that the machine would have to rely on brute force for, but I don't think there's actually any result to that effect.

▲

TheDong 6 months ago | parent | prev [-]

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.