4

Is detecting whether a deterministic program (i.e. state machine) is in an infinite loop equivalent to solving the halting problem?

I came up with a solution, and I'm not sure why it shouldn't work:

  • Let the program run
  • When you think it's in an infinite loop, take a snapshot of its memory regular intervals
  • If you ever detect the same snapshot, the program is in an infinite loop
  • As long as you don't get the same snapshot twice, it's either (1) not in an infinite loop, or (2) you need to take snapshots more quickly (perhaps once on every memory access?)

I'm assuming this doesn't work... but why?

It seems like a perfectly reasonable way to detect if a program is in an infinite loop (e.g. especially if you store hashes rather than the memory itself, although that will not be 100% accurate)... what's wrong with it, if anything?

Improve this question
2
  • This very thought came to me a few minutes ago, and I'm glad that someone else has already come up with it and cared to ask. Thanks. Commented Apr 24, 2012 at 13:34
  • I opened a similar question before seeing yours: stackoverflow.com/q/16250472/1858225 (Note that my question was also based on another question that I thought was prematurely closed.) I think rather than marking mine as a duplicate I'll just leave this comment here, since my question is a bit more specific and my answer distinguishes between this and the halting problem. Commented Apr 27, 2013 at 9:54

3 Answers 3

Reset to default
6

In theory, it is not equivalent to the halting problem because real computers have finite number of possible states (even though it's huge). Turing machines, which the halting problem applies to, have infinite storage.

But, let's explore your idea further. You also have to take a snapshot of the "hidden" state: the CPU's program counter and other registers, and that you must have to take a snapshot before each single instruction. (The program would be in an infinite loop if the memory snapshot is the same AND the same instruction is about to be executed. It doesn't help if the memory contents is the same, but something else is going to be executed than the last time you saw the same snapshot.)

In practice, even a very small computer has such a huge number of potential states that you'd never be able to store (not even hashes!) all your snapshots. For example, even a minicomputer like the ancient commodore 64 with 64kB of RAM has 256^65536 potential states (not including the 5 CPU registers). Tracking cycles that are potentially so long is absolutely infeasbile, both in time and space.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

The solution wouldn't work even in principle. A Turing machine doesn't have to ever be in precisely the same state (with the tape in the same configuration) to get into an infinite loop.

Your algorithm might work for context-sensitive languages and linear-bounded automata, but if you can't know how much tape a TM is going to need, you'd never know if you had an infinite loop or were about to hit the top. Note that your method would clearly work for real computers for a variety of reasons... chief among them being that your computer is less powerful than a (big) finite automaton.

Improve this answer

Comments

-3

I contacted one of the best experts in the field of the theory computation of about my own ideas on the halting problem and he gave me permission to quote him.

MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022 If simulating halt decider H correctly simulates its input D until H correctly determines that its simulated D would never stop running unless aborted then H can abort its simulation of D and correctly report that D specifies a non-halting sequence of configurations. MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022 typedef void (*ptr)(); typedef int (*ptr2)(); int H0(ptr P); int H(ptr2 P, ptr2 I); void Infinite_Loop() { HERE: goto HERE; } void Infinite_Recursion() { Infinite_Recursion(); } void DDD() { H0(DDD); } int P(ptr2 x) { int Halt_Status = H(x, x); if (Halt_Status) HERE: goto HERE; return Halt_Status; } int main() { H0(Infinite_Loop); H0(Infinite_Recursion); H0(DDD); H(P,P); }

Every C programmer that knows what an x86 emulator is knows that when H0 emulates the machine language of Infinite_Loop, Infinite_Recursion, and DDD that it must abort these emulations so that itself can terminate normally.

When this is construed as non-halting criteria then simulating termination analyzer H0 is correct to reject these inputs as non-halting by returning 0 to its caller.

It turns out that this same reasoning equally applies to H(P,P). It is impossible for the correctly emulated call to H(P,P) to return to P correctly emulated by H.

This same issue doesn't arise with the directly executed P(P) because the directly executed P(P) is essentially the first call in a recursive chain where the second call is always aborted.

If H(P,P) did not correctly recognize that it must abort the simulation of its input to correctly prevent its own non-termination the directly executed P(P) would never halt.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.