In computer science, a computation is said to diverge if it does not terminate or terminates in an exceptional state. 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

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

Rewriting

In abstract rewriting, an abstract rewriting system is called convergent if it is both confluent and

terminating In computer science, a computation is said to diverge if it does not terminate or terminates in an exceptional state. Otherwise it is said to converge. In domains where computations are expected to be infinite, such as process calculi, a computatio ...

. The notation ''t'' ↓ ''n'' 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 Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation ...

an expression is divergent if it has no normal form.

Denotational semantics

denotational semantics In computer science, denotational semantics (initially known as mathematical semantics or Scott–Strachey semantics) is an approach of formalizing the meanings of programming languages by constructing mathematical objects (called ''denotations'' ...

an object function ''f'' : ''A'' → ''B'' can be modelled as a mathematical function

f : A \cup\ \rightarrow B \cup\

where ⊥ ( bottom) indicates that the object function or its

argument An argument is a statement or group of statements called premises intended to determine the degree of truth or acceptability of another statement called conclusion. Arguments can be studied from three main perspectives: the logical, the dialectic ...

diverges.

Concurrency theory

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 CSP may refer to: Education * College Student Personnel, an academic discipline * Commonwealth Supported Place, a category in Australian education * Concordia University (Saint Paul, Minnesota), US Organizations * Caledonian Steam Packet Compa ...

notation: :

Clock = tick \rightarrow Clock

The traces of this process are defined as: :

\operatorname(Clock) = \ = \^*

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

P= Clock \backslash tick

By definition, ''P'' is called a divergent process.

Notes

References