Can you write a program to check to see if another program performs an infinite loop? There are many ‘good enough’ hacks/solutions out there to address this problem, but the true answer is a simple “no”. There are many proofs out there for this, and I would point you too look up the halting problem for more pointed discourse on this matter. This difficulty in detection is a core issue for a different and more annoying programming problem.
An infinite loop is, fortunately, a relatively obvious thing for a human programmer to spot and what is far more dangerous is a program that is ‘almost’ an infinite loop. In other words, a program that runs for a horribly long time but does actually conclude itself eventually. The most treacherous of these types of programs are problems that are termed NP-Complete.
What is NP-Complete? It’s a problem whose solutions seem obvious and easy, but the time required to come to those solutions can take a very long time. NP-Complete problems have no known solution that scales well with complexity. As the size and scope of the problem gets larger, the amount of time needed to find a solution rises exponentially.
This type of program, which works great for small test cases, crushes hardware utterly when faced with real usage. That is the danger of NP-Complete. One of our websites here at J House encountered this issue last year. We found that a search-and-match feature we were setting up was NP-Complete. The algorithm we intended to use would have easily worked for a very small number of users. For a medium or large number of users, the time for each individual search ran up into years or even decades. We realized the intractable nature of the problem and had to reduce the scope of the search. It was fortunate that we recognized this issue prior to actual programming.
The main weapon against such problems is awareness. Programmers should be able to recognize potentially NP-Complete problems and seek workarounds. The best way to raise awareness is to study examples. Well-known problems like the traveling salesman, N-Queens, and the knapsack are great examples of NP-Complete problems. They have all had extensive and well-documented studies conducted on them. Their details are out of the scope of this post, but I would direct you to start at the Wikipedia entry for NP-Complete problems as it is an excellently thorough and organized resource on this subject.
