Дивергенция (информатика)

В информатике говорят, что вычисление расходится, если оно не завершается или завершается в исключительном состоянии . ^{[1] : 377} В противном случае говорят, что оно сходится . В областях, где вычисления, как ожидается, будут бесконечными, таких как исчисления процессов , говорят, что вычисление расходится, если оно не может быть продуктивным (т. е. продолжать производить действие в течение конечного периода времени).

Различные разделы компьютерной науки используют разные, но математически точные определения того, что означает сходимость или расходимость вычисления.

В абстрактном переписывании абстрактная система переписывания называется конвергентной, если она является одновременно конфлюэнтной и завершающей . ^[2]

Запись t ↓ n означает, что t приводится к нормальной форме n за ноль или более редукций , t ↓ означает, что t приводится к некоторой нормальной форме за ноль или более редукций, а t ↑ означает, что t не приводится к нормальной форме; последнее невозможно в терминальной системе переписывания.

В лямбда-исчислении выражение является расходящимся, если оно не имеет нормальной формы . ^[3]

В денотативной семантике функция объекта f  : A → B может быть смоделирована как математическая функция , где ⊥ ( внизу ) указывает на то, что функция объекта или ее аргумент расходятся.${\displaystyle f:A\cup \{\perp \}\rightarrow B\cup \{\perp \}}$

В исчислении последовательных процессов связи (CSP) дивергенция — это драматическая ситуация, когда процесс выполняет бесконечную серию скрытых действий. Например, рассмотрим следующий процесс, определенный нотацией CSP:

${\displaystyle Часы=тик\rightarrow Часы}$

Следы этого процесса определяются как:

${\displaystyle \operatorname {traces} (Часы)=\{\langle \rangle ,\langle тик\rangle ,\langle тик,тик\rangle ,\cdots \}=\{тик\}^{*}}$

Теперь рассмотрим следующий процесс, который скрывает событие тика процесса Clock :

${\displaystyle P=Часы\обратная косая черта тик}$

По определению, P называется расходящимся процессом.

• Бесконечный цикл
• Анализ прекращения

• Баадер, Франц ; Нипков, Тобиас (1998). Переписывание терминов и все такое. Cambridge University Press. ISBN 9780521779203.
• Пирс, Бенджамин С. (2002). Типы и языки программирования . MIT Press.
• JMR Martin и SA Jassim (1997). «Как проектировать сети без тупиков с использованием CSP и инструментов проверки: введение в учебник» в трудах WoTUG-20 .

Эта статья по информатике — заглушка . Вы можете помочь Википедии, расширив ее.

• в
• т
• е