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

В информатике говорят, что вычисление расходится, если оно не завершается или завершается в исключительном состоянии . ^{[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 Clock=tick\rightarrow Clock}$

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

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

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

${\displaystyle P=Clock\backslash tick}$

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

Смотрите также

• Бесконечная петля
• Анализ завершения

Примечания

1. АВТОМОБИЛЬ Хоара (октябрь 1969 г.). «Аксиоматическая основа компьютерного программирования» (PDF) . Коммуникации АКМ . 12 (10): 576–583. дои : 10.1145/363235.363259. S2CID  207726175.
2. Баадер и Нипков 1998, с. 9.
3. Пирс 2002, с. 65.

Рекомендации

• Баадер, Франц ; Нипков, Тобиас (1998). Переписывание терминов и все такое. Издательство Кембриджского университета. ISBN 9780521779203.
• Пирс, Бенджамин К. (2002). Типы и языки программирования . МТИ Пресс.
• Дж. М. Р. Мартин и С. А. Джассим (1997). «Как спроектировать сети без тупиков с использованием CSP и инструментов проверки: введение в учебное пособие» в Proceedings of WoTUG-20 .