Aplikasi untuk teori himpunan, teori ordinal, kombinatorik tak terbatas dan topologi umum dalam ilmu komputer?

Saya seorang ahli matematika yang tertarik pada teori himpunan, teori ordinal, kombinatorik tak terbatas dan topologi umum.

Apakah ada aplikasi untuk mata pelajaran ini dalam ilmu komputer? Saya telah melihat sedikit, dan menemukan banyak aplikasi (tentu saja) untuk teori graf hingga, topologi terbatas, topologi dimensi rendah, topologi geometris dll.

Namun, saya mencari aplikasi objek tak terbatas dari subjek ini, yaitu pohon tak terbatas ( pohon Aronszajn misalnya), topologi tak terbatas dll.

Ada ide?

Terima kasih!!

Salah satu aplikasi utama topologi dalam semantik adalah pendekatan topologi untuk komputasi.

Ide dasar topologi komputabilitas berasal dari pengamatan bahwa terminasi dan nonterminasi tidak simetris. Dimungkinkan untuk mengamati apakah program kotak hitam berakhir (cukup tunggu cukup lama), tetapi tidak mungkin untuk mengamati apakah itu tidak berakhir (karena Anda tidak pernah bisa memastikan Anda belum menunggu cukup lama untuk melihatnya berakhir). Hal ini terkait dengan melengkapi dua set point {HALT, LOOP} dengan topologi Sierpinski, di mana $\emptyset, \{HALT\}, and \{HALT, LOOP\}$adalah set terbuka. Jadi pada dasarnya kita bisa menyamakan "set terbuka" dengan "properti yang dapat dihitung". Satu kejutan dari pendekatan terhadap topologi tradisional ini adalah peran sentral yang dimainkan oleh ruang-ruang non-Hausdorff. Ini karena Anda pada dasarnya dapat membuat identifikasi berikut

$$\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}$$

Dua survei yang bagus dari ide-ide ini adalah Topologi MB Smyth dalam Handbook of Logic dalam Ilmu Komputer dan topologi sintetis Martin Escardo tentang tipe data dan ruang klasik .

Metode topologis juga memainkan peran penting dalam semantik konkurensi, tetapi saya tahu sedikit tentang itu.

Hadiah Gödel 2004 dibagikan di antara makalah:

• Struktur Topologi Komputasi Asinkron .
  Oleh Maurice Herlihy dan Nir Shavit, Jurnal ACM, Vol. 46 (1999), 858-923
• Perjanjian Bebas-Tunggu k-Set Tidak Mungkin: Topologi Pengetahuan Publik .
  Oleh Michael Saks dan Fotios Zaharoglou, SIAM J. pada Computing, Vol. 29 (2000), 1449-1483.

Kutipan dari Hadiah Gödel 2004:

Kedua makalah ini menawarkan salah satu terobosan paling penting dalam teori komputasi terdistribusi.

Penemuan sifat topologi komputasi terdistribusi memberikan perspektif baru pada area tersebut dan merupakan salah satu contoh paling mencolok, mungkin dalam semua matematika terapan, tentang penggunaan struktur topologi untuk mengukur fenomena komputasi alami.

---

Posting terkait: Aplikasi topologi untuk ilmu komputer

Perilaku sistem reaktif sering dimodelkan menggunakan struktur tak hingga (pohon perhitungan tak terbatas dan tak terhingga) dan sifat temporal (sifat keselamatan dan daya tahan) juga dikarakterisasi menggunakan topologi.

Mendefinisikan Life Alpern dan Schneider

Keamanan dan Hidup dalam Waktu Percabangan Manolios et. Al.