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!!

user135172
quelle
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

Antworten:

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 ,{HEINLT},einnd{HEINLT,LÖÖP}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

CÖmputeinbichlichtyTÖpÖlÖGyArtPlatzBerechenbare FunktionDauerfunktionEntscheidbares SetClopen-SetHalbentscheidbares SetSet öffnenSet mit halbentscheidbarer ErgänzungGeschlossenes SetStellen Sie mit entscheidbarer Gleichheit einDiskreter RaumSet mit semidecidable GleichheitHausdorff RaumVollständig durchsuchbares SetKompakter Raum

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
NkN{k}NNN
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