Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Divergence (computer science)
Failure to reach a finite state after any finite amount of time in computer science

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

We don't have any images related to Divergence (computer science) yet.
We don't have any YouTube videos related to Divergence (computer science) yet.
We don't have any PDF documents related to Divergence (computer science) yet.
We don't have any Books related to Divergence (computer science) yet.
We don't have any archived web articles related to Divergence (computer science) yet.

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.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

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

Concurrency theory

See also: Communicating sequential processes § Failures/divergences model

In the calculus of communicating sequential processes (CSP), divergence occurs when a process performs an endless series of hidden actions.4 For example, consider the following process, defined by CSP notation: C l o c k = t i c k → C l o c k {\displaystyle Clock=tick\rightarrow Clock} The traces of this process are defined as: traces ⁡ ( C l o c k ) = { ⟨ ⟩ , ⟨ t i c k ⟩ , ⟨ t i c k , t i c k ⟩ , … } = { t i c k } ∗ {\displaystyle \operatorname {traces} (Clock)=\{\langle \rangle ,\langle tick\rangle ,\langle tick,tick\rangle ,\ldots \}=\{tick\}^{*}} Now, consider the following process, which hides the tick event of the Clock process: P = C l o c k ∖ t i c k {\displaystyle P=Clock\setminus tick} As P {\displaystyle P} cannot do anything other than perform hidden actions forever, it is equivalent to the process that does nothing but diverge, denoted d i v {\displaystyle \mathbf {div} } . One semantic model of CSP is the failures-divergences model, which refines the stable failures model by distinguishing processes based on the sets of traces after which they can diverge.

See also

Notes

References

  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. http://extras.springer.com/2002/978-3-642-63970-8/DVD3/rom/pdf/Hoare_hist.pdf

  2. Baader & Nipkow 1998, p. 9. - Baader, Franz; Nipkow, Tobias (1998). Term Rewriting and All That. Cambridge University Press. ISBN 9780521779203. https://books.google.com/books?id=N7BvXVUCQk8C&q=Divergent

  3. Pierce 2002, p. 65. - Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press.

  4. Roscoe, A.W. (2010). Understanding Concurrent Systems. Texts in Computer Science. doi:10.1007/978-1-84882-258-0. ISBN 978-1-84882-257-3. 978-1-84882-257-3