From Wikipedia, the free encyclopedia
Computation which does not terminate or terminates in an exceptional state
"Terminating" redirects here. For other uses, see
Termination.
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.[citation needed] 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).
Various subfields of computer science use varying, but mathematically precise, definitions of what it means for a computation to converge or diverge.
In abstract rewriting, an abstract rewriting system is called convergent if it is both confluent and terminating.
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.
Denotational semantics[edit]In denotational semantics an object function f : A → B 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[edit]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.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4