Divergence (computer science)

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

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 an expression is divergent if it has no normal form.[3]

In denotational semantics an object function f : A → B can be modelled as a mathematical function ${\displaystyle f:A\cup \{\perp \}\rightarrow B\cup \{\perp \}}$ where ⊥ (bottom) indicates that the object function or its argument diverges.

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:

${\displaystyle Clock=tick\rightarrow Clock}$

The traces of this process are defined as:

${\displaystyle \operatorname {traces} (Clock)=\{\langle \rangle ,\langle tick\rangle ,\langle tick,tick\rangle ,\cdots \}=\{tick\}^{*}}$

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

${\displaystyle P=Clock\backslash tick}$

By definition, P is called a divergent process.