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

«Завершение» перенаправляет сюда. Для использования в других целях см. Прекращение.

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

Определения

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

Перезапись

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

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

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

Денотационная семантика

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

Теория параллелизма

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

${displaystyle Clock=tickightarrow Clock}$

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

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

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

${displaystyle P=Clockackslash tick}$

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

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

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

Примечания

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

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

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