Infinite loop

From Esolang
Jump to: navigation, search

An infinite loop is a program that loops infinitely, never stopping. For example, the C program below:

main(){main();}

is an infinite loop.

That is an example of using recursion.

Another example using unconditional jumps:

main() {
    a:
         goto a;
}

Another using loops

main() {
    while(1);
}

Or, in pseudocode:

Forever:
    #we have nothing here

Implementability

Most languages which support loops can create an infinite loop via ensuring that the loop's termination condition will never be satisfied. However, there are some exceptions:

  • Some languages only support loops whose number of iterations is predictable in advance (e.g. wikipedia:BlooP). These languages tend to be primitive recursive. (The lack of an infinite loop inherently implies that a language is not Turing-complete.)
  • Some languages use a mechanism to ensure that all programs terminate (such as a finite supply of some resource that's required to run commands). Creating an intended-to-be-infinite loop in such a language will cause it to suddenly halt during some iteration of the loop.
  • Some languages have a built-in infinite loop detection (e.g. Incident), and will break out of a loop if they detect one. It is, however, often still possible to create an infinite loop in these languages via making it sufficiently complex that the language's infinite loop detector cannot detect it; but if the language's computational class is low enough (e.g. a finite state automaton), it's possible for the infinite loop detector to be perfect and thus for there to be no way to elude it.
  • Some languages are reversible. In this case, if it's possible for a program to enter an infinite loop (but it does not start in one), reversing program flow would break out of the loop after the number of iterations that had occurred so far. As such, an infinite loop in such a language must contain some sort of iteration counter (either directly or encoded in some way), unless the entire program is trivially an infinite loop; and in some languages (e.g. BackFlip, which has finite storage), such a counter is impossible to implement.

There might also be other reasons for which an infinite loop is impossible despite the language containing general-purpose looping constructs.