"The" kategori mesin Turing?

Penafian: Saya tahu sedikit tentang teori kompleksitas.

Maaf, tetapi benar-benar tidak ada cara untuk mengajukan pertanyaan ini tanpa (sangat) singkat:

Apa yang seharusnya menjadi morfisme dalam kategori "the" dari mesin Turing?

Ini jelas subyektif dan tergantung pada interpretasi seseorang terhadap teori, jadi jawaban untuk pertanyaan ini idealnya harus memberikan beberapa bukti dan alasan yang mendukung jawaban juga.

Saya ingin menekankan bahwa saya sedang mencari kategori mesin Turing dan bukan bahasa formal misalnya. Khususnya saya pikir morfisme saya harus mengandung informasi yang lebih baik kemudian pengurangan atau hal-hal seperti itu (saya tidak yakin).

Tentu saja jika sudah ada kategori yang terkenal dan digunakan dalam literatur saya ingin tahu apa itu.

cc.complexity-theory turing-machines ct.category-theory Saal Hardali
sumber

Anda mengatakannya sendiri - fungsi yang dapat dihitung.

Yuval Filmus

@Raphael masalahnya adalah Anda tidak pernah benar-benar mendefinisikan struktur sampai Anda memasukkannya ke dalam kategori. Saat itulah fitur yang tidak penting dari definisi spesifik dilucuti.

Saal Hardali

@SaalHardali Perlu diingat bahwa tidak semua orang menganut janji keselamatan yang dibuat oleh ahli teori kategori. Bahkan, banyak yang memutar mata.

Raphael

@ JoshuaGrochow Ada morfisme berlabel

dari

jika

mengurangi

(atau mungkin sebaliknya), yaitu

. Ini, katakanlah, untuk mesin yang pada setiap input berhenti atau tidak, tetapi tidak memiliki output lebih lanjut.

f

$f$

T_{1}

$T_1$

T_{2}

$T_2$

f

$f$

T_{2}

$T_2$

T_{1}

$T_1$

T_{1} (x) = T_{2} (f (x))

$T_1(x) = T_2(f(x))$

Yuval Filmus

Selain itu: mengapa TM harus menjadi objek? Mereka juga bisa jadi morfisme.

Martin Berger

Jawaban:

Saal Hardali menyebutkan bahwa dia menginginkan kategori mesin Turing untuk melakukan geometri (atau setidaknya teori homotopy). Namun, ada banyak cara berbeda untuk mencapai tujuan yang sama.

Ada analogi yang sangat kuat antara komputasi dan topologi. Intinya adalah bahwa penghentian / nonterminasi seperti ruang Sierpinski, karena penghentian dapat diamati secara halus (yaitu, terbuka) dan nonterminasi tidak (tidak terbuka). Lihat catatan kuliah Martin Escardo Topologi sintetik dari tipe data dan ruang klasik untuk pengenalan yang cukup lembut namun komprehensif untuk ide-ide ini.
Dalam perhitungan berbarengan dan didistribusikan, sering kali berguna untuk memikirkan kemungkinan eksekusi suatu program sebagai ruang, dan kemudian berbagai kendala sinkronisasi dapat dinyatakan sebagai properti homotopikal ruang tersebut. (Fakta bahwa eksekusi memiliki urutan waktu tampaknya lebih mengarah pada teori homotomi terarah, bukan teori homotomi biasa.)

Lihat artikel Eric Goubault Beberapa Perspektif Geometris tentang Teori Konkurensi untuk perincian lebih lanjut. Juga lihat makalah pemenang hadiah Goedel dari Niriceavllyy dan Nir Shavit, The Topological Structure of Asynchronous Computability , yang menyelesaikan beberapa masalah terbuka dalam teori pemrograman terdistribusi.
Gagasan ketiga datang melalui teori tipe homotopy, melalui penemuan bahwa teori tipe Martin-Lof (kemungkinan?) Adalah presentasi sintaksis (dalam arti generator dan hubungan) dari teori omega-groupoids - yaitu, model-model abstrak teori homotopy. Pengantar terbaik untuk ide-ide ini adalah buku teori jenis homotopy .

Perhatikan bahwa semua ide ini sangat berbeda satu sama lain, tetapi semua masih menggunakan intuisi geometris! Dan masih ada yang lain, yang saya tidak tahu, seperti kegunaan yang muncul dalam teori kompleksitas geometris, dan cara teori-teori sirkuit dapat dijelaskan dalam istilah (co) teori homologi grafik .

Pada dasarnya, ketika Anda melakukan CS, geometri adalah alat - Anda menggunakannya untuk memformalkan intuisi Anda, sehingga Anda bisa mendapatkan pengaruh melalui tubuh besar pekerjaan yang telah dilakukan di atasnya. Tapi itu penguat ide, bukan pengganti untuk punya ide!

Neel Krishnaswami
sumber

Jika objek Anda adalah mesin Turing, ada beberapa kemungkinan morfisme yang masuk akal. Sebagai contoh:

1) Pertimbangkan mesin Turing sebagai automata mereka, dan pertimbangkan morfisme automata yang biasa (peta antara huruf dan status yang konsisten satu sama lain) yang juga menjaga gerakan kepala pita, atau membalikkan secara tepat mereka (mis. kapan pun sumber TM ke kiri, target TM ke kanan dan sebaliknya).

2a) Pertimbangkan simulasi atau bisimulasi .

$T_1$ $T_2$ $f$ $T_1(x) = T_2(f(x))$ $x$

3) Pertimbangkan grafik transisi dari mesin Turing (setiap simpul adalah deskripsi lengkap tentang kondisi mesin dan kaset, dengan tepi terarah sesuai dengan transisi yang akan dibuat TM) dan pertimbangkan morfisme grafik. Untuk TM, ini adalah hubungan yang sangat kasar, karena pada dasarnya mengabaikan sifat komputasi lokal (mengabaikan, misalnya, apa isi kaset itu).

Saya pikir pertanyaan sebenarnya adalah: apa yang ingin Anda ketahui tentang TM atau hubungannya dengan mereka? Dengan tidak adanya hal ini, sulit untuk memberikan argumen untuk definisi apa pun atas yang lain, di luar kewajaran (dalam arti kata yang biasa, bukan makna kategorikal).

Joshua Grochow
sumber

Saya sangat baru dalam matematika semacam ini. Saya telah membaca di masa lalu tentang teori kompleksitas tetapi baru-baru ini saya mengambilnya kembali setelah saya melihat seseorang di internet mengklaim bahwa entah bagaimana teknik kohomologis akan memasuki teori kompleksitas pada abad berikutnya dan itu membuat saya tertarik. Setelah membaca beberapa kali, saya menyadari bahwa di luar pemahaman dangkal tentang definisi mesin turing, pada dasarnya saya tidak tahu apa yang dikodekan dengan tepat. Begitulah cara saya sampai pada pertanyaan. Jadi Anda dapat mengatakan bahwa pada tingkat yang sangat dasar saya mencoba membayangkan bagaimana kohomologi dapat memasuki teori kompleksitas.

Saal Hardali

Saya menyadari ini terlalu dini untuk seseorang seperti saya yang mengerti sedikit tentang topik ini, saya masih ingin sedikit bermain dengan ide ini di kepala saya "melakukan teori homotopy pada kategori mesin turing". Jawaban Anda bagus dan tentu saja saya ingin membaca lebih dalam tentang aspek-aspeknya. Terima kasih.

Saal Hardali

@ SaalHardali: Saya ingin tahu di mana Anda membaca bahwa kohomologi akan memasukkan teori kompleksitas? Saya dapat memikirkan dua cara, tetapi saya belum melihat rute melalui teori tipe homotopy (mungkin karena saya belum memahami HoTT dengan cukup baik). Dua cara yang bisa saya lihat: (1) dalam komputasi terdistribusi ini sudah terjadi, yaitu. Herlihy dan Rajsbaum, dan (2) melalui teori kompleksitas geometris.

Joshua Grochow

Dengan teori homotopy saya mengacu pada gagasan umum mempelajari kategori dengan ekuivalensi lemah dan tidak begitu banyak HoTT. Saya membacanya dalam jajak pendapat tentang P =? NP tidak sulit untuk menemukan Saya pikir itu terkait dengan salah satu pertanyaan di situs ini. Saya kira tebakan pertama saya (sebagai orang luar) adalah bahwa mungkin ada beberapa jenis ekuivalensi lemah yang menarik pada beberapa kategori model perhitungan yang sesuai dengan kelas kompleksitas, entah bagaimana, dan kemudian mempelajari functors yang tidak tetap di bawah ekuivalensi yang lemah itu akan membentuk apa yang saya sebut sebagai " teori homotopy "ini mungkin sangat naif dan total rindu.

Saal Hardali

Jika minat Anda adalah teori kompleksitas daripada teori komputabilitas, mungkin jawaban ini bermanfaat bagi Anda: cstheory.stackexchange.com/a/3422/4896

Sasho Nikolov

Anda mungkin tertarik dalam kategori Turing oleh Robin Cockett dan Pieter Hofstra. Dari sudut pandang teori kategori pertanyaan "apa yang kategori mesin Turing" kurang menarik daripada "apa struktur kategoris yang mendasari perhitungan". Dengan demikian, Robin dan Pieter mengidentifikasi jenis kategori umum yang cocok untuk mengembangkan teori komputabilitas. Lalu, ada beberapa kemungkinan untuk mendefinisikan kategori seperti itu mulai dari mesin Turing. Mengapa memiliki satu kategori ketika Anda dapat memiliki seluruh kategori tersebut?

Andrej Bauer
sumber