Infinite loop

related topics
{math, number, function}
{system, computer, user}

An infinite loop is a sequence of instructions in a computer program which loops endlessly, either due to the loop having no terminating condition, having one that can never be met, or one that causes the loop to start over. In older operating systems with cooperative multitasking, infinite loops normally caused the entire system to become unresponsive. With the now-prevalent preemptive multitasking model, infinite loops usually cause the program to consume all available processor time, but can usually be terminated by the user. Busy-wait loops are also sometimes misleadingly called "infinite loops". One possible cause of a computer "freezing" is an infinite loop; others include deadlock and access violations.

Like other terms with specific meaning to programmers and an evocative feel (for example memory leak), the term is sometimes used incorrectly; see colloquial use below. An actual infinite loop is something that can generally only be diagnosed by a programmer.

Contents

Looping

Looping is repeating a set of instructions until a specific condition is met. An infinite loop occurs when the condition will never be met, due to some inherent characteristic of the loop. There are a few situations when this is desired behavior. For example, the games on cartridge-based game consoles typically have no exit condition in their main loop, as there is no operating system for the program to exit to; the loop runs until console is powered off. Most often, the term is used for those situations when this is not the intended result; that is, when this is a bug. Such errors are most common among novice programmers, but can be made by experienced programmers as well, and their causes can be quite subtle.

Here is one example of an infinite loop in pseudocode:

REPEAT
x := 1;
x := x + 1;
UNTIL x > 5

This creates a situation where x will never be greater than 5, since at the start of the loop code x is given the value of 1, thus, the loop will always end in 2 and the loop will never break. This could be fixed by moving the SET x to 1 instruction outside the REPEAT loop.

A simple example of an infinite loop is instructing a computer to keep on adding 0 to 1 until 2 is reached. This will never happen.

One common cause, for example, is that the programmer intends to iterate over a collection of items such as a linked list, executing the loop code once for each item. Improperly formed links can create a reference loop in the list, causing the code to continue forever because the program never reaches the end of the list.

A simple example in BASIC:

DO
LOOP UNTIL 0

Here the loop is quite obvious, as the last line unconditionally sends execution back to the first. Unexpected behavior in evaluating the terminating condition can also cause this problem. Here is an example (in C):

float x = 0.1;
while (x != 1.1) {
  printf("x = %f\n", x);
  x = x + 0.1;
}

On some systems, this loop will execute ten times as expected, but on other systems it will never terminate. The problem is that the loop terminating condition (x != 1.1) tests for exact equality of two floating point values, and the way floating point values are represented in many computers will make this test fail, because they cannot represent the value 1.1 exactly.

Because of the likelihood of tests for equality or not-equality failing unexpectedly, it is safer to use greater-than or less-than tests when dealing with floating-point values. For example, instead of testing whether x equals 1.1, one might test whether (x <= 1.0), or (x < 1.1), either of which would be certain to exit after a finite number of iterations. Another way to fix this particular example would be to use an integer as a loop index, counting the number of iterations that have been performed.

A similar problem occurs frequently in numerical analysis: in order to compute a certain result, an iteration is intended to be carried out until the error is smaller than a chosen tolerance. However, because of rounding errors during the iteration, the specified tolerance can never be reached, resulting in an infinite loop.

The simplest example (in C):

while(1) {
  printf("Infinite Loop\n");
}

This is a loop that will forever print "Infinite Loop."

While most infinite loops can be found by close inspection of the code, there is no general method to determine whether a given program will ever halt or will run forever; this is the undecidability of the halting problem.

Full article ▸

related documents
Pseudorandomness
Logo (programming language)
NaN
Shell script
Generating trigonometric tables
Latin square
Bresenham's line algorithm
Vi
INTERCAL
Monotone convergence theorem
Column space
Cotangent space
Operator overloading
Quasigroup
Special linear group
Associative algebra
Borel algebra
Automata theory
Graftal
Golden ratio base
Stirling's approximation
Sylow theorems
Theory of computation
Least common multiple
Interpolation search
Jacobi symbol
1 (number)
Bilinear transform
Free variables and bound variables
Measure (mathematics)