4

How would you determine a loop is a infinite loop and will break out of it.

Does anyone has the algorithm or can assist me on this one.

Thanks

Improve this question
4
  • 2
    My guess is that there's no sure way that computer recognizes something as infinite loop. You have to be aware of it as a code engineer. Commented Mar 16, 2012 at 14:01
  • But some intelligent language compiler understand and get you out of the loop if such thing happens. Commented Mar 16, 2012 at 14:03
  • 3
    It's easy, just wait for infinity and see if the program has terminated. Commented Mar 16, 2012 at 14:03
  • While I don't think @amit's response below is logically valid, I also don't think there always exists a way to determine if something will loop indefinitely. For example, you could always construct a function whose limit (for some value of parameters) cannot be calculated except numerically---thus you would have to perform the calculation to tell if some end case would result or not (and thus if the loop would perform one way or another). In special cases, making the determination could be done easily analytically, or by trial of the loop.... Commented Mar 16, 2012 at 15:46

2 Answers 2

Reset to default
8

There is no general case algorithm that can determine if a program is in an infinite loop or not for every turing complete language, this is basically the Halting Problem.

The idea of proving it is simple:

  1. Assume you had such an algorithm A.
  2. Build a program B that invokes A on itself [on B].
  3. if A answers "the program will halt" - do an infinite loop
  4. else [A answers B doesn't halt] - halt immidiately

Now, assume you invoke A on B - the answer will be definetly wrong, thus A doesn't exist.

Note: the above is NOT a formal proof, just a sketch of it.

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

2 Comments

OK..what if you are said to traverse a long row of data that is connected to some point of same row. Is this a particular case of Halting problem or you have any algo associated to solve it?
@PankajGupta: If I am not mistaken - for each program A, there is a program B that can determine if A will halt. There is no general case algorithm, that can determine if a program halts or not - for all programs.
5

As written by others, it cannot be determined.

However, if you want to have some checking, you can use the WatchDog design pattern. This is a separate thread that checks if a task still is active. Your own thread should give a signal regularly to say it is alive. Make sure this signal is not set inside your (infinite) loop.

If there was no signal, the program is inside an infinite loop or has stopped and the watchdog can act on it.

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.