Divergencia (informática)

En informática , se dice que un cálculo diverge si no termina o termina en un estado excepcional . ^{[1] : 377} De lo contrario, se dice que converge . En dominios donde se espera que los cálculos sean infinitos, como los cálculos de procesos , se dice que un cálculo diverge si no es productivo (es decir, si continúa produciendo una acción dentro de una cantidad finita de tiempo).

Varios subcampos de la informática utilizan definiciones diferentes, pero matemáticamente precisas, de lo que significa que un cálculo converja o diverja.

En la reescritura abstracta , un sistema de reescritura abstracta se denomina convergente si es a la vez confluente y terminal . ^[2]

La notación t ↓ n significa que t se reduce a la forma normal n en cero o más reducciones , t ↓ significa que t se reduce a alguna forma normal en cero o más reducciones, y t ↑ significa que t no se reduce a una forma normal; esto último es imposible en un sistema de reescritura terminal.

En el cálculo lambda, una expresión es divergente si no tiene forma normal . ^[3]

En semántica denotacional, una función objeto f  : A → B se puede modelar como una función matemática donde ⊥ ( bottom ) indica que la función objeto o su argumento diverge. ${\displaystyle f:A\cup \{\perp \}\rightarrow B\cup \{\perp \}}$

En el cálculo de procesos secuenciales comunicativos (CSP), la divergencia es una situación drástica en la que un proceso realiza una serie interminable de acciones ocultas. Por ejemplo, considere el siguiente proceso, definido mediante la notación CSP:

${\displaystyle Reloj=tick\rightarrow Reloj}$

Las huellas de este proceso se definen como:

${\displaystyle \operatorname {rastros} (Reloj)=\{\langle \rangle ,\langle tick\rangle ,\langle tick,tick\rangle ,\cdots \}=\{tick\}^{*}}$

Ahora, considere el siguiente proceso, que oculta el evento tick del proceso Clock :

${\displaystyle P=tic de barra invertida del reloj}$

Por definición, P se denomina proceso divergente.

• Bucle infinito
• Análisis de terminación

• Baader, Franz ; Nipkow, Tobias (1998). Reescritura de términos y todo eso. Cambridge University Press. ISBN 9780521779203.
• Pierce, Benjamin C. (2002). Tipos y lenguajes de programación . MIT Press.
• JMR Martin y SA Jassim (1997). "Cómo diseñar redes sin interbloqueos utilizando herramientas de verificación y CSP: una introducción al tutorial" en Actas de WoTUG-20 .