Penerapan tesis Church-Turing untuk model komputasi interaktif

Paul Wegner dan Dina Goldin telah lebih dari satu dekade menerbitkan makalah dan buku dengan alasan utama bahwa tesis Church-Turing sering salah diartikan dalam komunitas Teori CS dan di tempat lain. Yaitu, ia disajikan sebagai mencakup semua perhitungan padahal sebenarnya itu hanya berlaku untuk perhitungan fungsi, yang merupakan bagian yang sangat kecil dari semua perhitungan. Sebagai gantinya mereka menyarankan kita harus mencari model komputasi interaktif, di mana komunikasi dengan dunia luar terjadi selama perhitungan.

Satu-satunya kritik yang saya lihat dari karya ini adalah di forum Lambda the Ultimate , di mana seseorang menyesalkan penulis ini karena terus menerbitkan apa yang jelas-jelas diketahui. Pertanyaan saya kemudian adalah, apakah ada lagi kritik terhadap garis pemikiran ini, dan khususnya Mesin Turing Persisten mereka. Dan jika tidak, mengapa itu tampaknya dipelajari sangat sedikit (saya bisa saja salah). Terakhir, bagaimana pengertian universalitas diterjemahkan ke domain interaktif.

Inilah analogi favorit saya. Misalkan saya menghabiskan satu dekade menerbitkan buku dan makalah dengan alasan bahwa, berlawanan dengan dogma ilmu komputer teoretis, Tesis Gereja-Turing gagal menangkap semua perhitungan, karena mesin Turing tidak dapat memanggang roti . Oleh karena itu, Anda memerlukan model baru revolusioner saya , Mesin Turing-Enhanced Turing (TETM), yang memungkinkan roti sebagai input yang mungkin dan memasukkan pemanggangan sebagai operasi primitif.

Anda mungkin berkata: tentu, saya punya "poin", tapi itu benar-benar tidak menarik. Tidak ada yang pernah mengklaim bahwa mesin Turing dapat menangani setiap kemungkinan interaksi dengan dunia luar, tanpa terlebih dahulu menghubungkannya ke periferal yang sesuai. Jika Anda ingin TM memanggang roti, Anda harus menghubungkannya ke pemanggang roti; maka TM dapat dengan mudah menangani logika internal pemanggang (kecuali pemanggang roti khusus ini membutuhkan pemecahan masalah penghentian atau sesuatu seperti itu untuk menentukan seberapa cokelat roti yang seharusnya!). Dengan cara yang persis sama, jika Anda ingin TM menangani komunikasi interaktif, maka Anda perlu menghubungkannya ke perangkat komunikasi yang sesuai, seperti yang dibahas Neel dalam jawabannya. Dalam kedua kasus kita tidak mengatakan sesuatu yang tidak jelas bagi Turing sendiri.

Jadi, saya akan mengatakan alasan mengapa tidak ada "tindak lanjut" terhadap kecaman Wegner dan Goldin adalah bahwa TCS telah mengetahui cara memodelkan interaktivitas kapan pun diperlukan, dan telah melakukannya dengan senang hati, sejak awal mula.

Pembaruan (8/30): Poin terkait adalah sebagai berikut. Apakah itu pernah memberikan kritik jeda bahwa, di sini di dalam Menara Gading-Turing Gereja Elite (ECTIT), tema penelitian utama selama dua dekade terakhir telah termasuk bukti interaktif, protokol kriptografi multipartai, kode untuk komunikasi interaktif, protokol asinkron untuk routing , konsensus, penyebaran rumor, pemilihan pemimpin, dll., dan harga anarki dalam jaringan ekonomi? Jika menempatkan konsep perhitungan Turing di tengah lapangan membuatnya sangat sulit untuk membahas interaksi, bagaimana mungkin begitu sedikit dari kita yang memperhatikan?

Pembaruan Lainnya: Bagi orang-orang yang terus-menerus menggedor tentang formalisme tingkat tinggi yang jauh lebih intuitif daripada TM, dan tidak ada yang berpikir dalam hal TM sebagai masalah praktis, izinkan saya mengajukan pertanyaan yang sangat sederhana. Apa yang memungkinkan semua bahasa tingkat tinggi itu ada di tempat pertama, yang memastikan mereka selalu dapat dikompilasi ke kode mesin? Mungkinkah ... err ... TESIS GEREJA-TURING ini , yang sama dengan yang pernah Anda bicarakan? Untuk memperjelas, Tesis Gereja-Turing bukanlah klaim bahwa "MENGUBAH ATURAN ATURAN !!" Sebaliknya, itu adalah klaim bahwa bahasa pemrograman yang masuk akal akan setara dalam kekuatan ekspresif untuk mesin Turing - dan sebagai konsekuensinya, bahwa Anda mungkin juga berpikir dalam hal bahasa tingkat yang lebih tinggi jika lebih mudah untuk melakukannya. Ini, tentu saja, adalah wawasan baru yang radikal 60-75 tahun yang lalu.

Pembaruan Akhir: Saya telah membuat posting blog untuk diskusi lebih lanjut tentang jawaban ini.

Saya pikir masalahnya cukup sederhana.

1. Semua formalisme interaktif dapat disimulasikan oleh mesin Turing.

2. TM adalah bahasa yang tidak nyaman untuk penelitian tentang komputasi interaktif (dalam banyak kasus) karena isu-isu menarik tenggelam dalam kebisingan pengkodean.

3. Semua orang yang bekerja pada matematika interaksi tahu ini.

Biarkan saya jelaskan ini secara lebih rinci.

Mesin Turing jelas dapat memodelkan semua model komputasi interaktif yang ada dalam pengertian berikut: Pilih beberapa pengkodean sintaksis yang relevan sebagai string biner, tulis TM yang mengambil dua input program interaktif yang dikodekan P, Q (dalam model komputasi interaktif pilihan) dan mengembalikan true tepat ketika ada pengurangan satu langkah dari P ke Q dalam sistem penulisan ulang istilah yang relevan (jika kalkulus Anda memiliki hubungan transisi ternary, lanjutkan secara mutatis mutandis). Jadi, Anda mendapatkan TM yang melakukan simulasi perhitungan langkah demi langkah dalam kalkulus interaktif. Jelas pi-kalkulus, ambient kalkulus, CCS, CSP, Petri-nets, pi-kalkulus waktunya dan model komputasi interaktif lain yang telah dipelajari dapat diekspresikan dalam pengertian ini. Inilah yang dimaksud orang ketika mereka mengatakan interaksi tidak melampaui TM.

N. Krishnaswami mengacu pada pendekatan kedua untuk pemodelan interaktivitas menggunakan kaset oracle. Pendekatan ini berbeda dari interpretasi relasi reduksi / transisi di atas, karena gagasan TM diubah: kita berpindah dari TM biasa ke TM dengan kaset oracle. Pendekatan ini populer dalam teori kompleksitas dan kriptografi, terutama karena memungkinkan peneliti di bidang ini untuk mentransfer alat dan hasil dari sekuensial ke dunia bersamaan.

Masalah dengan kedua pendekatan tersebut adalah bahwa masalah teoretis konkurensi sejati dikaburkan. Teori concurrency berusaha memahami interaksi sebagai fenomena sui generis. Kedua pendekatan melalui TM hanya menggantikan formalisme yang nyaman untuk mengekspresikan bahasa pemrograman interaktif dengan formalisme yang kurang nyaman.

Dalam kedua pendekatan itu tidak ada masalah teori konkurensi sejati, yaitu komunikasi dan infrastruktur pendukungnya memiliki representasi langsung. Mereka ada di sana, terlihat oleh mata yang terlatih, tetapi dikodekan, disembunyikan dalam kabut kerumitan pengkodean yang tidak dapat ditembus. Jadi kedua pendekatan tersebut buruk dalam hal matematika, sebagai keprihatinan utama komputasi interaktif. Ambil contoh apa yang mungkin merupakan ide terbaik dalam teori bahasa pemrograman dalam setengah abad terakhir, aksiomatissi ekstrusi lingkup Milner et al (yang merupakan langkah kunci dalam teori umum komposisionalitas):

Betapa indahnya ide ini ketika diekspresikan dalam bahasa yang dibuat khusus seperti pi-calculus. Melakukan ini menggunakan pengkodean pi-kalkulus ke TMs mungkin akan mengisi 20 halaman.

Dengan kata lain, penemuan formalisme eksplisit untuk interaksi telah membuat kontribusi berikut untuk ilmu komputer: axiomatisasi langsung dari primitif kunci untuk komunikasi (misalnya operator input dan output) dan mekanisme pendukung (misalnya pembuatan nama baru, komposisi paralel, dll) . Aksiomaasi ini telah berkembang menjadi tradisi penelitian yang sesungguhnya dengan konferensi, sekolah, dan terminologinya sendiri.

Situasi serupa diperoleh dalam matematika: sebagian besar konsep dapat ditulis menggunakan bahasa teori himpunan (atau teori topos), tetapi kami lebih suka konsep tingkat yang lebih tinggi seperti kelompok, cincin, ruang topologi dan sebagainya.

$\mathbb{N} \to \mathbb{N}$

Namun, masih benar bahwa mesin Turing cukup menyakitkan untuk pemodelan properti seperti interaktivitas. Alasannya agak halus, dan ada hubungannya dengan jenis pertanyaan yang ingin kita tanyakan tentang perhitungan interaktif.

Lulus pertama yang biasa pada interaksi pemodelan dengan TM adalah dengan pita oracle. Secara intuitif, Anda dapat menganggap string yang dicetak pada pita oracle sebagai "prediksi" dari interaksi I / O mesin Turing dengan lingkungan. Namun, pertimbangkan jenis pertanyaan yang ingin kami tanyakan tentang program interaktif: misalnya, kami mungkin ingin tahu bahwa program komputer tidak akan menampilkan data keuangan Anda kecuali menerima nama pengguna dan kata sandi Anda sebagai input, dan selanjutnya program tidak bocor informasi tentang kata sandi. Membicarakan kendala semacam ini sangat menyakitkan dengan string oracle, karena mencerminkan batasan temporal, epistemik pada jejak interaksi, dan definisi kaset oracle meminta Anda untuk memasok seluruh string di depan.

Saya menduga mendapatkan hak ini bisa dilakukan, dan pada dasarnya jumlah (1) untuk mempertimbangkan string oracle bukan sebagai satu set, tetapi sebagai ruang topologi yang set terbuka menyandikan logika modal waktu dan pengetahuan yang ingin Anda modelkan, dan (2) memastikan bahwa teorema yang Anda buktikan semuanya berkesinambungan sehubungan dengan topologi ini, memandang predikat sebagai fungsi kontinu dari string oracle hingga nilai kebenaran yang dipandang sebagai ruang Sierpinski. Saya harus menekankan bahwa ini adalah dugaan , berdasarkan analogi dengan teori domain. Anda harus mengetahui detailnya (dan mungkin mengirimkannya ke LICS atau sesuatu) untuk memastikannya.

Akibatnya, orang lebih suka memodelkan interaksi menggunakan hal-hal seperti model Dolev-Yao , di mana Anda secara eksplisit memodelkan interaksi antara komputer dan lingkungan, sehingga Anda dapat secara eksplisit mengkarakterisasi apa yang diketahui penyerang. Ini membuatnya lebih mudah untuk merumuskan logika modal yang tepat untuk alasan keamanan, karena keadaan sistem ditambah keadaan lingkungan diwakili secara eksplisit.

membaca blog Lance Fortnows, baru saja membaca artikel survei baru-baru ini / bagus / panjang tentang subjek dengan banyak perspektif & referensi [1] (yang belum dikutip sejauh ini), termasuk perspektif Wegner / Goldin (di antara banyak lainnya). Saya hanya akan mengutip Fortnows ringkasan / deklarasi / pernyataan tegas yang tegas / tegas dari garis partai TCS yang hampir resmi / seragam / dengan suara bulat:

"Beberapa ilmuwan komputer tetap mencoba untuk berpendapat bahwa tesis [Gereja-Turing] gagal untuk menangkap beberapa aspek perhitungan. Beberapa dari ini telah diterbitkan di tempat-tempat bergengsi seperti Sains, Komunikasi ACM, dan sekarang sebagai seluruh rangkaian makalah di ACM Ubiquity. Beberapa orang di luar ilmu komputer mungkin berpikir bahwa ada perdebatan serius tentang sifat komputasi. Tidak ada. "

[1] Mesin Turing Titanic oleh Barry S Cooper CACM Vol 55

Saya sangat setuju dengan komentar Aaronson.

Saya tidak mengerti pekerjaan Milner. (misalnya pi kalkulus, yang diciptakan Milner untuk menggambarkan proses komunikasi). Bagi saya, ini tidak dapat dibaca, seperti hampir semua makalah tentang matematika dan logika, seperti teori Lambek. Saya tidak ragu bahwa ide-ide Lambek sangat bagus, tetapi saya ingin melihatnya diterjemahkan ke dalam semacam bahasa Inggris pidgin yang dapat saya baca.

Saya terlempar oleh komentar Milner bahwa kalkulus lambda baik-baik saja untuk "proses sekuensial" tetapi ada sesuatu yang lebih dibutuhkan untuk proses komunikasi.

Pandangan saya (mungkin naif) adalah yang tidak bisa begitu, karena pi-kalkulus adalah Turing lengkap, dan karena itu dapat dikonversi secara mekanis ke notasi Turing-lengkap lainnya, yaitu lambda calculus. Oleh karena itu notasi pi-kalkulus Milner dapat dikonversi secara otomatis ke kalkulus lambda.

Tampaknya saya telah mengidentifikasi proyek: secara intuitif, seharusnya memungkinkan untuk secara mekanis mengkonversi dari satu bahasa Turing-lengkap ke yang lain. apakah ada algoritma untuk melakukan ini? Saya harus mencari di Google. Mungkin ini sangat sulit dilakukan, dan sama sulitnya dengan masalah penghentian.

Saya melihat kemarin di internet, dan menemukan makalah tentang model kalkulus lambda. Saya terkejut menemukan bahwa ini tampaknya lubang kelinci yang sangat dalam.

Richard Mullins

Begini masalahnya, setelah Anda menambahkan interaktivitas (murni), formalitas keluar jendela. Ini bukan lagi sistem "tertutup". Pertanyaannya kemudian adalah, apa pengertian komputasi setelah interaktivitas masuk? Jawaban itu: baik, pengguna lain / mesin menggantikan beberapa perhitungan Anda (yang dapat ditentukan oleh mesin negara lain yang lebih besar) atau Anda tidak lagi berada dalam sistem yang dapat ditentukan secara formal dan sekarang Anda bermain sebuah permainan , dalam hal tidak ada aplikasi dari tesis Gereja-Turing.

membaca makalah Wegner, jelas dia agak melodramatik dan pelawan, tetapi dia ada benarnya. masa depan komputasi bisa dibilang jauh lebih signifikan berpusat di robotika , AI , atau datamining (dari "data besar" dunia nyata yang luas) yang tampaknya tidak banyak disebut namanya, tetapi yang jelas ia singgung dengan modelnya. dan area-area ini sangat banyak fokus pada alam semesta di luar input dan output TM.

secara historis itu juga pergi dengan nama sibernetika sebagai diciptakan / dirumuskan oleh Weiner. Inti dari robotika adalah bahwa input dan output tidak hanya digital dan tanpa makna, yang dapat disimpulkan dengan melihat TM; mereka, tetapi mereka memiliki implikasi / efek / penyebab dunia nyata dll, dan mesin membentuk loop umpan balik dengan lingkungan.

jadi saya akan berpendapat bahwa TM dan robotika membentuk hubungan sinergi atau simbiotik yang sangat alami. tetapi ini bukan pernyataan radikal dan apa yang Wegner umumkan dengan kemeriahan luar biasa adalah, diutarakan dalam istilah yang berbeda, tidak terlalu kontroversial atau novel. dengan kata lain, Wegner tampaknya menempatkan dirinya sebagai ikonoklas intelektual atau akademis dalam gayanya dengan sengaja ... jadi siapa komunitas TCS yang menyangkalnya dari framing melodramatik itu? namun lihat [2] untuk bantahan yang serius.

Contoh Wegner tentang mengendarai mobil sangat relevan & terobosan baru lainnya dalam TCS dapat dikutip:

• tantangan balapan DARPA dan juga Google mendekati teknologi mobil penggerak. [3]
• kasus kemenangan catur Big Blue AI atas Kasparov
• kemenangan Deep Blue Jeopardy Challenge baru-baru ini
• penjelajah Mars yang semakin otonom
• terobosan yang baru-baru ini diumumkan dalam pengenalan objek tanpa pengawasan oleh Google. [4]
• pengenalan ucapan yang dikomersialkan

tetapi memang benar, apa yang dimulai beberapa dekade yang lalu sebagai teori belaka dengan TMs sekarang merupakan fenomena dunia nyata dan segmen menara gading komunitas TCS mungkin berada dalam beberapa perlawanan atau bahkan penolakan terhadap fakta itu dan terkait, fundamental [dekat Kuhnian ] transformasi dan pergeseran "saat ini dalam permainan". ini agak ironis karena Turing sangat diterapkan dalam banyak perspektif & studinya seperti minatnya dalam tes AI operasional (tes Turing), dinamika kimia, perhitungan pemecahan catur, dll [5].

Anda bahkan dapat melihat ini dalam mikrokosmos di situs ini dalam bentrokan tentang cara mendefinisikan ruang lingkup, dan argumen panas tentang apakah tag spesifik yang tampaknya tidak berbahaya yang disebut application-of-theory adalah sah. [7]

dan mari kita perhatikan bahwa sebenarnya TCS sedang mempelajari banyak model komputasi interaktif dan banyak penelitian utama sedang berlangsung di bidang itu ... terutama sistem bukti interaktif yang semua kelas komputasi penting dapat didefinisikan dalam istilah. [6]

[1] Tesis Gereja-Turing - mematahkan mitos oleh Goldin & Wegner

[2] Apakah ada model komputasi yang baru? balasan untuk Goldin & Wegner oleh Cockshott & Michaelson

[3] Googles self-driving cars - 300 ribu mil yang ditebang, bukan kecelakaan tunggal di bawah kendali komputer, Atlantik

[4] Pengakuan objek Google tanpa pengawasan gambar Youtube

[5] Kontribusi Alan Turings ke CS

[6] Lansekap sistem bukti interaktif

[7] Tentang memodifikasi ruang lingkup kami - sebuah proposal