Interpretasi Geometrik dari Komputasi

Menjadi dari Fisika, saya telah dilatih untuk melihat banyak masalah dari sudut pandang geometris. Misalnya geometri diferensial manifold dalam sistem dinamik dll. Ketika saya membaca dasar-dasar ilmu komputer, saya selalu berusaha menemukan interpretasi geometris. Seperti interpretasi geometris yang masuk akal dari set enumerable rekursif (saya bekerja pada bagian di mana saya mencoba menghubungkannya dengan Aljabar Geometri dengan mengeksploitasi ekuivalensi dengan Diophantine Sets tetapi hubungannya tampak dipaksakan dan saya tidak dapat menemukan ungkapan "alami" dari fakta-fakta dalam hal itu. formulasi) atau hasil geometris yang indah untuk algoritma sederhana untuk menyortir angka. Meskipun saya bukan seorang ahli, saya telah membaca survei tentang Teori Kompleksitas Geometris dan tentunya ini adalah program yang menarik tetapi saya lebih tertarik untuk memiliki pandangan geometris konsep yang sangat mendasar seperti dinamika Mesin Turing, Kalkulus Lambda atau struktur ( un) set yang dapat dihitung (bukan masalah khusus). Apakah ini pekerjaan yang sia-sia untuk menemukan struktur geometris pada objek-objek ini atau dapatkah seseorang mengharapkan beberapa hasil yang rumit? Apakah ada formulasi TCS yang memperlakukannya secara geometris?

Semantik program komputer dapat dipahami secara geometris dalam tiga cara berbeda (dan tampaknya tidak kompatibel).

• Pendekatan tertua adalah melalui teori domain . Intuisi di balik teori domain muncul dari asimetri di balik terminasi dan nonterminasi.

  Ketika memperlakukan program secara ekstensi (yaitu, hanya melihat perilaku I / O mereka, dan bukan struktur internal mereka), selalu mungkin untuk mengkonfirmasi dalam waktu terbatas bahwa suatu program berhenti - Anda hanya menunggu sampai berhenti. Namun, tidak mungkin untuk mengonfirmasi bahwa suatu program tidak berhenti, karena tidak peduli berapa lama Anda menunggu, selalu ada program berhenti yang akan berjalan selama beberapa langkah lebih banyak daripada yang Anda tunggu.

  Akibatnya, penghentian dan pengulangan dapat dilihat sebagai pembentukan ruang topologi ( ruang Sierpiński ). Ini mengangkat ke gagasan pengamatan yang lebih kaya (melalui topologi Scott), dan dengan demikian Anda dapat menafsirkan program sebagai elemen ruang topologi. Ruang-ruang ini umumnya cukup mengejutkan dari sudut pandang tradisional - domain umumnya bukan Hausdorff.

  Pengantar topologi terbaik yang saya tahu tentang ide-ide ini adalah Topologi singkat dan sangat mudah diakses Steve Vickers via Logic . Ini dapat dipahami sebagai semacam pemanasan untuk Ruang Batu Peter Johnstone yang jauh lebih tangguh .

  Jika Anda mencari catatan kuliah online, izinkan saya menyarankan Topologi Sintetik Tipe Data dan Ruang Klasik Martin Escardo .

• Pandangan lain muncul dari teori konkurensi. Program bersamaan dapat dipahami sebagai memiliki beberapa eksekusi yang valid (urutan negara bagian), tergantung pada bagaimana ras diselesaikan. Kemudian, himpunan eksekusi dapat dilihat sebagai ruang, dengan setiap urutan keadaan yang mungkin dipahami sebagai jalur melalui ruang ini. Kemudian, metode dari topologi aljabar dan teori homotopy dapat diterapkan untuk mendapatkan invarian tentang pelaksanaan program.

  Nir Shavit dan Maurice Herlihy menggunakan ide ini untuk membuktikan ketidakmungkinan algoritma terdistribusi tertentu, yang mana mereka memenangkan hadiah Gödel 2004. (Lihat Struktur Topologi Komputasi Asinkron .) Eric Goubault memiliki makalah survei yang menjelaskan ide-ide yang relevan dalam Beberapa Perspektif Geometris dalam Teori Concurrency .

• Baru-baru ini, telah diamati bahwa struktur tipe identitas dalam teori tipe dependen berhubungan sangat erat dengan gagasan tipe homotop dalam teori homotop - sangat dekat, pada kenyataannya, bahwa teori tipe dependen sebenarnya dapat dilihat sebagai semacam "teori homotopty sintetik"! (Vladimir Voevodsky bercanda bahwa ia menghabiskan beberapa tahun mengembangkan kalkulus baru untuk teori homotopy, hanya untuk menemukan bahwa rekan-rekannya di departemen CS sudah mengajarkannya kepada mahasiswa sarjana.)

  Lihat tautan cody di atas ke buku teori jenis homotopy .

Menariknya, ketiga pandangan ini tampaknya tidak cocok satu sama lain, atau setidaknya sangat sulit untuk didamaikan. Teori tipe dependen adalah bahasa total, sehingga nonterminasi (dan topologi Scott) tidak muncul di dalamnya. Ini juga konfluen, sehingga pandangan komputasi-sebagai-spasi tidak muncul juga. Demikian pula, merumuskan konkurensi dalam hal teori domain terbukti sangat sulit, dan akun yang sepenuhnya memuaskan masih merupakan masalah terbuka.

Seperti yang terjadi begitu saja, telah ada perkembangan baru-baru ini dalam teori tipe dependen , di mana suatu tipe, yang secara tradisional mewakili invarian statis untuk program komputer, dapat diartikan sebagai ruang topologi, atau lebih tepatnya kelas ekivalen seperti spasi ( tipe homotopy ).

Ini telah menjadi subjek penelitian intensif selama beberapa tahun terakhir, yang memuncak dalam sebuah buku .

$\lambda$

Anda mengetahui GCT, tetapi Anda mungkin tidak menyadarinya Mulmuley sebelumnya tentang menunjukkan pemisahan antara subset dari perhitungan PRAM dan P, yang menggunakan ide-ide geometris tentang bagaimana perhitungan dapat dilihat sebagai mengukir ruang.

Banyak batas bawah untuk masalah dalam model pohon keputusan aljabar berkurang menjadi alasan tentang topologi ruang solusi yang mendasari (angka Betti muncul sebagai parameter yang relevan).

Di satu sisi, SEMUA optimasi adalah geometris: program linear melibatkan menemukan titik terendah dari sebuah polytope dalam dimensi tinggi, SDPs adalah fungsi linear di atas ruang matriks semidefinite, dan sebagainya. Geometri banyak digunakan dalam desain algoritma di sini.

Pada tema itu, ada hubungan yang panjang dan mendalam antara kemampuan kami untuk mengoptimalkan fungsi-fungsi tertentu pada grafik dan kemampuan kami untuk menanamkan ruang metrik di ruang bernorma tertentu. Ini adalah literatur yang sangat luas sekarang.

Akhirnya, dalam beberapa tahun terakhir telah ada banyak minat dalam apa yang disebut "lift-and-project" mekanisme untuk memecahkan masalah optimasi, dan ini sangat memanfaatkan geometri yang mendasari dan mengangkat ke ruang dimensi yang lebih tinggi: gagasan dari permainan geometri aljabar peran penting di sini.

$T_1$

Salah satu cara untuk memahami hubungan antara pemrosesan informasi (juga dikenal sebagai "perhitungan") dan geometri adalah bahwa pemrosesan informasi adalah pra- geometri. Pandangan ini harus familier dari bagian fisika tertentu. Misalnya dalam teori relativitas kita mempelajari struktur sebab - akibat dari ruangwaktu (pemrosesan informasinya) serta struktur geometrisnya . Banyak yang akan menganggap yang terakhir lebih mendasar daripada yang sebelumnya.

Koneksi ini telah diperhatikan di masa lalu dan beberapa tahun yang lalu ada upaya untuk menghubungkan aspek informasi-teoretis dari ilmu komputer dengan teori relativitas. Salah satu tugas yang ingin diselesaikan orang adalah: mulai dari struktur kausalitas ruangwaktu (yang hanya merupakan urutan parsial pada ruangwaktu), merekonstruksi topologi ruangwaktu, atau mungkin juga geometri. Memulihkan topologi dari urutan parsial adalah jenis teori domain yang bagus, sehingga ada beberapa keberhasilan.

Referensi:

• Struktur Komputasi untuk Memodelkan Ruang, Waktu dan Kausalitas , Seminar Dagstuhl 06341, 20-25 Agustus 2006

• Kunci Martin dan Prakash Panangaden: Geometri ruangwaktu dari struktur sebab akibat dan pengukuran

$U$

menafsirkan pertanyaan Anda secara kreatif, beberapa kemungkinan selain GCT seperti yang Anda sebutkan muncul dalam pikiran. salah satu caranya adalah mencari masalah yang tidak dapat dipastikan (alias kelengkapan Turing) yang cukup di mana-mana.

• aperiodik . Ubin bidang & ubin Penrose . telah terbukti bahwa pertanyaan apakah ada ubin aperodik pada pesawat tidak dapat diputuskan.

• Automata seluler yang juga semakin terbukti memiliki koneksi yang mendalam dengan fisika, banyak masalah terkait yang tidak dapat diputuskan, TM lengkap, dan mereka secara alami ditafsirkan sebagai (dan dikonversikan antara) tableaus komputasi TM.

• $(x,y)$

• Ketidakpastian dalam sistem dinamik (Hainry), lagi-lagi terkadang berhubungan erat dengan fisika. sistem dinamis umumnya memiliki interpretasi geometris multidimensi.

• Bahasa pemrograman visual . sebuah program dapat dilihat sebagai jenis grafik (terarah?) dengan berbagai jenis simpul (mis. kondisional, operasi aritmatika) dll.