Приложения для теории множеств, порядковой теории, бесконечной комбинаторики и общей топологии в информатике?

15

Я математик, интересующийся теорией множеств, порядковой теорией, бесконечной комбинаторикой и общей топологией.

Есть ли приложения для этих предметов в информатике? Я немного посмотрел и нашел много приложений (конечно) для теории конечных графов, конечной топологии, низкоразмерной топологии, геометрической топологии и т. Д.

Однако я ищу приложения бесконечных объектов этих предметов, то есть бесконечных деревьев ( например, деревьев Аронсайна ), бесконечной топологии и т. Д.

Есть идеи?

Спасибо!!

set-theory topology topological-graph-theory user135172
источник
1
см. также Применение предметов теории множеств в качестве ординалов, форсирующих, общих фильтров в программной инженерии. cs.se
vzn
2
В дополнение к великолепному ответу Нила вас могут заинтересовать вычислимые ординалы, которые играют интересную роль в теории вычислимости: en.wikipedia.org/wiki/Recursive_ordinal
Джошуа Грохоу,

Ответы:

21

Одним из основных применений топологии в семантике является топологический подход к вычислимости.

Основная идея топологии вычислимости исходит из наблюдения, что завершение и нетерминация не симметричны. Можно наблюдать, завершается ли программа черного ящика (просто ждать достаточно долго), но невозможно наблюдать, не завершается ли она (поскольку вы никогда не можете быть уверены, что не подождали достаточно долго, чтобы увидеть, как она завершится). Это соответствует оснащению двухточечного набора {HALT, LOOP} топологией Серпинского, где являются открытыми наборами. Таким образом, мы можем довольно далеко отождествить «открытый набор» с «вычислимым свойством». Одним из сюрпризов такого подхода к традиционным топологам является центральная роль, которую играют не хаусдорфовы пространства. Это потому, что вы можете сделать следующие идентификации∅,{ЧАСALT},aNd{ЧАСALT,LООп}

СомпUTaбяLяTYTопоLограммYТипКосмосВычислимая функцияНепрерывная функцияРешаемый наборЗакрытый наборПолуразрешимый наборОткрытый наборНабор с полуразрешимым дополнениемЗакрытый наборНабор с разрешимым равенствомДискретное пространствоМножество с полуразрешимым равенствомХаусдорфово пространствоИсчерпывающий поискКомпактное пространство

Два хороших обзора этих идей - топология М.Б. Смита в « Руководстве по логике в информатике» и « Синтетическая топология типов данных и классических пространств» Мартина Эскардо .

Топологические методы также играют важную роль в семантике параллелизма, но я знаю об этом гораздо меньше.

Нил Кришнасвами
источник
Спасибо за ваш поучительный ответ! Я взгляну.
user135172
Можно ли искать более точную топологию только для полиномиальной иерархии?
T ....
1
Увлекательное применение этих идей можно найти в серии постов «На первый взгляд
jkff
1
Можете ли вы дать нам немного больше здесь? Я нахожу этот ответ очень трудным для понимания. Например, предположим для противоречия, что полуразрешимые подмножества образуют топологию, как вы, похоже, заявляете. Тогда из этого следует, что, поскольку для любого натурального числа одноэлементное множество является полуразрешимым, поэтому произвольные объединения одноэлементных подмножеств полуразрешимы. Следовательно, каждое подмножество полуразрешимо, противоречие. k ∈ N { k } ⊆ N N NNК∈N{К}⊆NNN
Гоблин
4

Приз Геделя 2004 года был поделен между газетами:

  • Топологическая структура асинхронных вычислений .
    Морис Херлихи и Нир Шавит, Журнал ACM, Vol. 46 (1999), 858-923
  • Соглашение K-Set без ожидания: топология публичного знания .
    Майкл Сакс и Фотос Захароглу, SIAM J. по вычислительной технике, Vol. 29 (2000), 1449-1483.

Цитаты из премии Геделя 2004 года:

Эти две статьи предлагают один из самых важных прорывов в теории распределенных вычислений.

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

Связанный пост: Приложения топологии к информатике

Hengxin
источник
3
Хотя это, безусловно, отличное применение топологии в TCS, они на самом деле являются приложениями «комбинаторной / алгебраической топологии», а не того, что, как мне кажется, ОП подразумевает под «общей топологией» (что больше в теории точек / теории множеств / логики арена).
Джошуа Грохов
4

Поведение реактивной системы часто моделируется с использованием бесконечных структур (бесконечные трассируемые и бесконечные деревья вычислений), а их временные свойства (свойства безопасности и живучести) также характеризуются с помощью топологии.

Определение жизненности Alpern и Schneider

Безопасность и жизнедеятельность в ветвящемся времени Manolios et. и др.

Митеш Дж
источник