Remix clone Hacker News

This approach suffers from two major problems:

* It makes computability and complexity dependent on individual machines (now a program may halt on machine A, but not on machine B). For various reasons, we don't want that.

* The entire state space of a single machine consists of all the registers, memory cells, etc. But keeping track of all states that have been visited before requires exponentially more space than the space that is actually available on the machine (because you're computing the powerset). So the machine itself can't solve its halting problem, only a much more powerful one can.

Very often, impossibility results in infinitary mathematics translate back to "there's no reasonable way to do this" in actual practice where things are finite.

▲

Ukv 6 days ago | parent [-]

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 days 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 days 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 days 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.