Zastosowania teorii mnogości, teorii porządkowej, nieskończonej kombinatoryki i ogólnej topologii w informatyce?

15

Jestem matematykiem zainteresowanym teorią zbiorów, teorią porządkową, nieskończoną kombinatoryką i topologią ogólną.

Czy są jakieś zastosowania dla tych przedmiotów w informatyce? Szukałem trochę i znalazłem wiele zastosowań (oczywiście) do teorii grafów skończonych, topologii skończonej, topologii niskowymiarowej, topologii geometrycznej itp.

Szukam jednak zastosowań nieskończonych obiektów tych podmiotów, tj. Drzew nieskończonych ( na przykład drzew Aronszajna ), nieskończonej topologii itp.

Jakieś pomysły?

Dziękuję Ci!!

set-theory topology topological-graph-theory

— użytkownik135172
źródło

1

patrz także Zastosowanie przedmiotów teorii mnogości jako porządków, wymuszania, filtrów ogólnych w inżynierii oprogramowania cs.se

— od

2

Oprócz świetnej odpowiedzi Neela, być może zainteresują cię również obliczalne porządki, które odgrywają interesującą rolę w teorii obliczeń: en.wikipedia.org/wiki/Recursive_ordinal

— Joshua Grochow

21

Jednym z głównych zastosowań topologii w semantyce jest topologiczne podejście do obliczalności.

Podstawowa koncepcja topologii obliczalności wynika z obserwacji, że zakończenie i nieterminacja nie są symetryczne. Można zaobserwować, czy program czarnej skrzynki się kończy (wystarczy poczekać wystarczająco długo), ale nie można zaobserwować, czy się nie kończy (ponieważ nigdy nie możesz być pewien, że nie czekałeś wystarczająco długo, aby się zakończył). Odpowiada to wyposażeniu zestawu dwóch punktów {HALT, LOOP} w topologię Sierpińskiego, gdzie $\emptyset, \{HALT\}, and \{HALT, LOOP\}$ są otwarte zestawy. Zatem możemy zasadniczo zrównać „otwarty zestaw” z „właściwością obliczalną”. Jedną niespodzianką tego podejścia do tradycyjnych topologów jest centralna rola przestrzeni spoza Hausdorffa. Wynika to z faktu, że można w zasadzie dokonać następujących identyfikacji

\begin{matrix} do o m p u t za b ja l ja t y & T. o p o l o sol y \\ Rodzaj & Przestrzeń \\ Funkcja obliczalna & Funkcja ciągła \\ Zestaw rozstrzygalny & Zestaw Clopen \\ Zestaw częściowo rozstrzygalny & Otwórz zestaw \\ Zestaw z półstabilnym uzupełnieniem & Zestaw zamknięty \\ Zestaw z rozstrzygającą równością & Dyskretna przestrzeń \\ Ustaw z równą półdecydowalności & Przestrzeń Hausdorffa \\ Kompletny zestaw do przeszukiwania & Kompaktowa przestrzeń \end{matrix}

$\begin{matrix} \mathbf{Computability} & \mathbf{Topology}\\ \mbox{Type} & \mbox{Space} \\ \mbox{Computable function} & \mbox{Continuous function} \\ \mbox{Decidable set} & \mbox{Clopen set} \\ \mbox{Semi-decidable set} & \mbox{Open set} \\ \mbox{Set with semidecidable complement} & \mbox{Closed set} \\ \mbox{Set with decidable equality} & \mbox{Discrete space} \\ \mbox{Set with semidecidable equality} & \mbox{Hausdorff space} \\ \mbox{Exhaustively searchable set} & \mbox{Compact space} \\ \end{matrix}$

Dwa dobre badania tych pomysłów to Topologia MB Smyth w Handbook of Logic in Computer Science oraz Topologia syntetyczna Martina Escardo typów danych i klasycznych przestrzeni .

Metody seologiczne również odgrywają ważną rolę w semantyce współbieżności, ale wiem o tym znacznie mniej.

— Neel Krishnaswami
źródło

Dziękuję za twoją oświecającą odpowiedź! Spojrzę na to.

— user135172

Czy możliwe jest poszukiwanie lepszej topologii samej hierarchii wielomianowej?

— T ....

1

Fascynujące zastosowanie tych pomysłów można znaleźć w serii postów „Pozornie niemożliwe programy funkcjonalne” - math.andrej.com/2007/09/28/… , math.andrej.com/2014/05/08/seemingly-impossible -proofs

— jkff

1

N

$\mathbb{N}$

k \in N

$k \in \mathbb{N}$

{k} \subseteq N

$\{k\} \subseteq \mathbb{N}$

N

$\mathbb{N}$

N

$\mathbb{N}$

4

Nagroda Gödela z 2004 roku została podzielona między gazety:

Topologiczna struktura obliczeń asynchronicznych .
Autorzy: Maurice Herlihy i Nir Shavit, Journal of the ACM, t. 46 (1999), 858–923
Umowa k-set bez czekania jest niemożliwa: topologia wiedzy publicznej .
Autorzy: Michael Saks i Fotios Zaharoglou, SIAM J. on Computing, t. 29 (2000), 1449-1483.

Cytaty z nagrody Gödela 2004 roku:

Oba artykuły stanowią jeden z najważniejszych przełomów w teorii przetwarzania rozproszonego.

Odkrycie topologicznej natury obliczeń rozproszonych zapewnia nowe spojrzenie na ten obszar i stanowi jeden z najbardziej uderzających przykładów, być może we wszystkich zastosowanej matematyce, zastosowania struktur topologicznych do kwantyfikacji naturalnych zjawisk obliczeniowych.

Temat powiązany: Zastosowania topologii w informatyce

— hengxin
źródło

3

Chociaż są to z pewnością świetne zastosowania topologii w TCS, tak naprawdę są to zastosowania „topologii kombinatorycznej / algebraicznej”, a nie tego, co myślę, że OP rozumiał przez „topologię ogólną” (która jest bardziej w teorii punktowej / teoretycznej / logicznej arena).

— Joshua Grochow

4

Zachowanie się układu reaktywnego jest często modelowane przy użyciu struktur nieskończonych (drzewa obliczeniowe o nieskończonym kształcie i nieskończone), a ich właściwości doczesne (właściwości bezpieczeństwa i żywotności) zostały również scharakteryzowane przy użyciu topologii.

Definiowanie żywotności Alpern i Schneider

Bezpieczeństwo i żywotność w czasie rozgałęzienia Manolios i in. glin.

— Mitesh J
źródło