Anwendungen für Mengenlehre, Ordinaltheorie, Infinite Combinatorics und allgemeine Topologie in der Informatik?

15

Ich bin Mathematiker und interessiere mich für Mengenlehre, Ordinaltheorie, unendliche Kombinatorik und allgemeine Topologie.

Gibt es Bewerbungen für diese Fächer in der Informatik? Ich habe ein bisschen nachgesehen und (natürlich) viele Anwendungen für die Theorie der endlichen Graphen, die endliche Topologie, die niedrigdimensionale Topologie, die geometrische Topologie usw. gefunden.

Ich suche jedoch nach Anwendungen der unendlichen Objekte dieser Subjekte, dh unendliche Bäume ( zum Beispiel Aronszajn-Bäume ), unendliche Topologie usw.

Irgendwelche Ideen?

Vielen Dank!!

set-theory topology topological-graph-theory user135172
quelle

1

siehe auch Anwendung von Mengen-Theorie-Fächern als Ordnungszahlen, Erzwingen, generische Filter in der Softwareentwicklung cs.se

vzn 30.04.15

2

Zusätzlich zu der großartigen Antwort von Neel könnten Sie auch an berechenbaren Ordnungszahlen interessiert sein, die eine interessante Rolle in der Berechnungstheorie spielen: en.wikipedia.org/wiki/Recursive_ordinal

Joshua Grochow

21

Eine wichtige Anwendung der Topologie in der Semantik ist der topologische Ansatz zur Berechenbarkeit.

Die Grundidee der Topologie der Berechenbarkeit beruht auf der Beobachtung, dass Terminierung und Nicht-Terminierung nicht symmetrisch sind. Es ist möglich zu beobachten, ob ein Black-Box-Programm beendet wird (einfach lange genug warten), aber es ist nicht möglich zu beobachten, ob es nicht beendet wird (da Sie niemals sicher sein können, dass Sie nicht lange genug gewartet haben, um zu sehen, dass es beendet wird). Dies entspricht die Ausstattung der zwei Punktsatz {HALT, LOOP} mit der Sierpinski Topologie, wobei $\emptyset, \{HALT\}, and \{HALT, LOOP\}$ sind die offenen Sätze. Also können wir es im Grunde ziemlich weit bringen, "offene Menge" mit "berechenbarer Eigenschaft" gleichzusetzen. Eine Überraschung dieses Ansatzes für traditionelle Topologen ist die zentrale Rolle, die Nicht-Hausdorff-Räume spielen. Dies liegt daran, dass Sie grundsätzlich die folgenden Identifikationen vornehmen können

\begin{matrix} C Ö m p u t ein b ich l ich t y & T Ö p Ö l Ö G y \\ Art & Platz \\ Berechenbare Funktion & Dauerfunktion \\ Entscheidbares Set & Clopen-Set \\ Halbentscheidbares Set & Set öffnen \\ Set mit halbentscheidbarer Ergänzung & Geschlossenes Set \\ Stellen Sie mit entscheidbarer Gleichheit ein & Diskreter Raum \\ Set mit semidecidable Gleichheit & Hausdorff Raum \\ Vollständig durchsuchbares Set & Kompakter Raum \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}$

Zwei gute Überblicke über diese Ideen sind MB Smyths Topologie im Handbuch der Logik in der Informatik und Martin Escardos Synthetische Topologie von Datentypen und klassischen Räumen .

Topologische Methoden spielen auch eine wichtige Rolle in der Semantik der Parallelität, aber ich weiß viel weniger darüber.

Neel Krishnaswami
quelle

Vielen Dank für Ihre aufschlussreiche Antwort! Ich werde nachsehen.

user135172

Ist es möglich, eine feinere Topologie nur für die Polynomhierarchie zu suchen?

T ....

1

Eine faszinierende Anwendung dieser Ideen findet sich in der Reihe der Beiträge "Scheinbar unmögliche Funktionsprogramme" - 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

Der Gödel-Preis 2004 wurde zwischen den Vorträgen aufgeteilt:

Die topologische Struktur der asynchronen Berechnung .
Von Maurice Herlihy und Nir Shavit, Journal of the ACM, Vol. 46 (1999), 858 & ndash; 923
Eine wartefreie k-Set-Vereinbarung ist unmöglich: Die Topologie des öffentlichen Wissens .
Von Michael Saks und Fotios Zaharoglou, SIAM J. on Computing, Bd. 29 (2000), 1449 & ndash; 1483.

Zitate aus dem Gödel-Preis 2004:

Die beiden Arbeiten bieten einen der wichtigsten Durchbrüche in der Theorie des Distributed Computing.

Die Entdeckung der topologischen Natur des verteilten Rechnens bietet eine neue Perspektive auf das Gebiet und ist eines der auffälligsten Beispiele, möglicherweise in der gesamten angewandten Mathematik, für die Verwendung topologischer Strukturen zur Quantifizierung natürlicher Rechenphänomene.

Verwandter Beitrag: Anwendungen der Topologie in der Informatik

Hengxin
quelle

3

Obwohl dies sicherlich großartige Anwendungen der Topologie in TCS sind, handelt es sich tatsächlich um Anwendungen der "kombinatorischen / algebraischen Topologie", und nicht um die, wie ich meine , unter "allgemeiner Topologie" (die eher in der Punkttheorie / Mengenlehre / Logik liegt) verstandene OP Arena).

Joshua Grochow

4

Das Verhalten eines reaktiven Systems wird häufig mit Hilfe von unendlichen Strukturen (infinite traced und infinite computation trees) modelliert, und ihre zeitlichen Eigenschaften (Sicherheits- und Lebendigkeitseigenschaften) wurden ebenfalls mit Hilfe der Topologie charakterisiert.

Lebensfreude definieren Alpern und Schneider

Sicherheit und Lebendigkeit in der Verzweigungszeit Manolios et. al.

Mitesh J
quelle

Anwendungen für Mengenlehre, Ordinaltheorie, Infinite Combinatorics und allgemeine Topologie in der Informatik?

Antworten: