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

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

Определения

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

Перезапись

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

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

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

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

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

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

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

{displaystyle Clock = часы со стрелкой-стрелкой}

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

{displaystyle operatorname {traces} (Часы) = {угол наклона, угол наклона, угол наклона, угол наклона, cdots} = {отметка} ^ {*}}

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

{displaystyle P = Clock ackslash tick}

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

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

Примечания

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