Английская Википедия:Divergence (computer science)

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Redirect In computer science, a computation is said to diverge if it does not terminate or terminates in an exceptional state.Шаблон:Rp 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.Шаблон:Sfn

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.Шаблон:Sfn

Denotational semantics

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

Concurrency theory

In the calculus of communicating sequential processes (CSP), 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:

<math>Clock = tick \rightarrow Clock</math>

The traces of this process are defined as:

<math>\operatorname{traces}(Clock) = \{\langle\rangle, \langle tick \rangle, \langle tick,tick \rangle, \cdots \} = \{ tick \}^*</math>

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

<math>P= Clock \backslash tick</math>

By definition, P is called a divergent process.

See also

• Infinite loop
• Termination analysis

References

• Шаблон:Cite book
• Шаблон:Cite book
• J. M. R. Martin and S. A. Jassim (1997). "How to Design Deadlock-Free Networks Using CSP and Verification Tools: A Tutorial Introduction" in Proceedings of the WoTUG-20.

Шаблон:Comp-sci-stub