In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, a computation is said to diverge if it does not terminate or terminates in an exceptional
state
State most commonly refers to:
* State (polity), a centralized political organization that regulates law and society within a territory
**Sovereign state, a sovereign polity in international law, commonly referred to as a country
**Nation state, a ...
.
Otherwise it is said to converge. In domains where computations are expected to be infinite, such as
process calculi
In computer science, the process calculi (or process algebras) are a diverse family of related approaches for formally modelling concurrent systems. Process calculi provide a tool for the high-level description of interactions, communications, and ...
, 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
In mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviated ARS) is a Formalism (mathematics), formalism that captures the quintessential notion and ...
, an
abstract rewriting system
In mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviated ARS) is a formalism that captures the quintessential notion and properties of rewriting ...
is called convergent if it is both
confluent
Confluent, Inc. is an American technology company headquartered in Mountain View, California. Confluent was founded by Jay Kreps, Jun Rao and Neha Narkhede on September 23, 2014, in order to commercialize an open-source streaming platform Apa ...
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
In mathematical logic, the lambda calculus (also written as ''λ''-calculus) is a formal system for expressing computability, computation based on function Abstraction (computer science), abstraction and function application, application using var ...
an expression is divergent if it has no
normal form.
Denotational semantics
In
denotational semantics
In computer science, denotational semantics (initially known as mathematical semantics or Scott–Strachey semantics) is an approach of formalizing the meanings of programming languages by constructing mathematical objects (called ''denotations'' ...
an
object function ''f'' : ''A'' → ''B'' can be modelled as a
mathematical function
In mathematics, a function from a set (mathematics), set to a set assigns to each element of exactly one element of .; the words ''map'', ''mapping'', ''transformation'', ''correspondence'', and ''operator'' are sometimes used synonymously. ...
where ⊥ (
bottom) indicates that the object function or its
argument
An argument is a series of sentences, statements, or propositions some of which are called premises and one is the conclusion. The purpose of an argument is to give reasons for one's conclusion via justification, explanation, and/or persu ...
diverges.
Concurrency theory
In the calculus of
communicating sequential processes
In computer science, communicating sequential processes (CSP) 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 p ...
(CSP), divergence occurs when 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 hides the ''tick'' event of the ''Clock'' process:
As
cannot do anything other than perform hidden actions forever, it is equivalent to the process that does nothing but diverge, denoted
. 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
*
Infinite loop
In computer programming, an infinite loop (or endless loop) is a sequence of instructions that, as written, will continue endlessly, unless an external intervention occurs, such as turning off power via a switch or pulling a plug. It may be inte ...
*
Termination analysis
In computer science, termination analysis is program analysis which attempts to determine whether the evaluation of a given program halts for ''each'' input. This means to determine whether the input program computes a ''total'' function.
It is ...
Notes
References
*
*
* 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''.
Programming language theory
Process (computing)
Rewriting systems
Lambda calculus
Denotational semantics
{{comp-sci-stub