Divergence (computer science)
Encyclopedia
In computer science
, a computation is said to diverge if it does not terminate or terminates in an (unobservable) 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 (always produces an action within a finite amount of time.)
In the lambda calculus
an expression is divergent if it has no normal form.
an object function f : A → B can be modelled as a mathematical function
f : A ∪ {⊥} → B ∪ {⊥} where ⊥ (bottom) indicates that the object function or its argument diverges.
, 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:
The traces of this process are defined as:
Now, consider the following process, which conceals the tick event of the Clock process:
By definition, P is called a divergent process.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a computation is said to diverge if it does not terminate or terminates in an (unobservable) 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 (always produces an action within a finite amount of time.)
Definitions
Various subfields of computer science use a varying, but mathematically precise, definitions of what it means for a computation to converge or diverge.Rewriting
In abstract rewriting a reduction is called convergent if and only if it is both confluent and terminating. The notation t ↓ n means term 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.In the lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
an expression is divergent if it has no normal form.
Denotational semantics
In denotational semanticsDenotational semantics
In computer science, denotational semantics is an approach to formalizing the meanings of programming languages by constructing mathematical objects which describe the meanings of expressions from the languages...
an object function f : A → B can be modelled as a mathematical function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
f : A ∪ {⊥} → B ∪ {⊥} where ⊥ (bottom) indicates that the object function or its argument diverges.
Concurrency theory
In the calculus of communicating sequential processesCommunicating sequential processes
In computer science, Communicating Sequential Processes is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or process calculi...
, divergence is a drastic situation where a process performs an endless series of hidden actions. For example, consider the following process, defined by CSP
Communicating sequential processes
In computer science, Communicating Sequential Processes is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or process calculi...
notation:
The traces of this process are defined as:
Now, consider the following process, which conceals the tick event of the Clock process:
By definition, P is called a divergent process.