Divergence (computer science)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In computer science, a computation is said to diverge if it does not terminate or terminates in an exceptional state.[1]: 377  Otherwise it is said to converge. In domains where computations are expected to be infinite, such as process calculi, a computation is said to diverge if it fails to be productive (i.e. to continue producing an action within a finite amount of time).

Definitions[edit]

Various subfields of computer science use varying, but mathematically precise, definitions of what it means for a computation to converge or diverge.

Rewriting[edit]

In abstract rewriting, an abstract rewriting system is called convergent if it is both confluent and terminating.[2]

The notation tn means that t reduces to normal form n in zero or more reductions, t↓ means t reduces to some normal form in zero or more reductions, and t↑ means t does not reduce to a normal form; the latter is impossible in a terminating rewriting system.

In the lambda calculus an expression is divergent if it has no normal form.[3]

Denotational semantics[edit]

In denotational semantics an object function f : AB can be modelled as a mathematical function where ⊥ (bottom) indicates that the object function or its argument diverges.

Concurrency theory[edit]

In the calculus of communicating sequential processes, divergence is a drastic situation where a process performs an endless series of hidden actions. For example, consider the following process, defined by CSP notation:

The traces of this process are defined as:

Now, consider the following process, which conceals the tick event of the Clock process:

By definition, P is called a divergent process.

See also[edit]

Notes[edit]

  1. ^ C.A.R. Hoare (Oct 1969). "An Axiomatic Basis for Computer Programming" (PDF). Communications of the ACM. 12 (10): 576–583. doi:10.1145/363235.363259. S2CID 207726175.
  2. ^ Baader & Nipkow 1998, p. 9.
  3. ^ Pierce 2002, p. 65.

References[edit]