Formalisasi Seperti Mesin Turing untuk Model Aktor

8

Mesin Turing memiliki alfabet simbol formal , status dan deskripsi transisi-aturan berdasarkan bagaimana komputasi dilakukan.

Actor Model kadang-kadang disebut sebagai model komputasi yang lebih kuat daripada mesin Turing (bukan pada apa yang dapat dikomputasi, tetapi dalam aspek lain).

  1. Apakah The Actor Model merupakan alternatif mesin Menghidupkan penuh sebagai model komputasi?
  2. Apakah Model Aktor juga memiliki deskripsi perhitungan formal berbasis simbol seperti mesin Turing?
  3. Apakah para aktor diasumsikan setara dengan mesin Turing - karena setiap pesan diproses secara berurutan (dan secara atomis)?

Ada banyak hasil teoretis yang didasarkan pada mesin Turing, misalnya masalah penghentian, kepastian keputusan, kaitan dengan teorema ketidaklengkapan Gödel, dll.

Bisakah bukti-bukti ini secara umum digeneralisasi ke Model Aktor? Apakah ini sudah dilakukan?

terminology computability reference-request programming-languages computation-models Adi Shavit
sumber
1
Saya pikir aktor (seperti dalam Erlang) biasanya dianggap Turing lengkap. Namun, ada penelitian besar tentang semua jenis automata yang bekerja sama. Ada juga proses kalkulus . Saya pikir pertanyaannya lebih luas dari yang Anda perkirakan. Mungkin Anda harus memfokuskan pertanyaan dengan memberikan contoh spesifik dari sistem yang Anda inginkan untuk memiliki model formal, sehingga orang dapat melihat apa yang Anda cari.
Raphael
@ Raphael: Apakah Anda memiliki referensi bahwa aktor dalam Model Aktor diasumsikan Turing lengkap? Saya tertarik pada dasar-dasar perhitungan dengan model seperti itu.
Adi Shavit
Itu benar-benar tergantung di mana Anda mengambil istilah "model aktor" dari. Saya tahu dari Erlang dan perpustakaan untuk bahasa lain yang meniru Erlang, dan mereka tidak memiliki batasan pada kekuatan aktor tunggal (karenanya mereka, dalam dunia teori, Turing-complete). Ngomong-ngomong, artikel Wikipedia yang Anda tautkan menyediakan banyak referensi ; sudahkah anda memeriksanya? Lihat juga yang ini .
Raphael
1
Googling sekitar saya menemukan makalah baru-baru ini dengan hasil yang bagus tentang Turing kelengkapan dan decidability
Vor
1
The pi kalkulus datang ke pikiran, yang merupakan proces bate sebagai negara oleh @Raphael di atas. Ini adalah model perhitungan (Turing-complete, karena dapat menyandikan kalkulus lambda). Semua model perhitungan setara menghadapi masalah yang sama (seperti pada: tidak ada satu pun dari mereka yang dapat memecahkan masalah penghentian, dll).
paulotorrens

Jawaban:

-2

ilmuwan komputer umumnya dari konsensus bahwa tesis Gereja Turing [1] adalah benar dan definitif, yaitu bahwa mesin Turing menggambarkan perhitungan, dan bahwa bentuk yang lebih kuat tidak benar-benar ada, dan mengambil pernyataan bahwa beberapa model "lebih kuat" daripada Turing mesin dengan skeptisisme ekstrim, bahkan di dekat permusuhan. [2] Neophytes ke bidang yang tidak sepenuhnya memahami konsep adalah mangsa slogan pemasaran dekat beberapa teori sebagai "lebih kuat" dari mesin Turing tetapi klaim itu jarang dibuat oleh ilmuwan komputer arus utama / terkemuka.

tetapi sebagai sisi lain dari ini, banyak model perhitungan Turing lengkap. oleh karena itu dalam CS sebagian besar dalam praktiknya ada sikap toleran, "hidup dan biarkan hidup" dengan banyak model komputasi yang berkembang biak bergantung pada apa yang paling relevan dan nyaman untuk masalah yang dipelajari. kebanyakan model pemrograman dasar adalah Turing lengkap dengan struktur dasar seperti memori, kondisional, dan loop, subrutin dan sebagainya. jadi klaim yang lebih masuk akal adalah, "model [x] lebih cocok untuk mempelajari [y] karena [z]". model Aktor berfokus pada pengiriman pesan, komunikasi, konkurensi & keamanan.

namun demikian ada sebagian besar perdebatan filosofis dalam CS tentang beberapa model yang "lebih kuat".

[1] Tesis Gereja Turing

[2] Model komputasi interaktif vs tesis Church Turing

vzn
sumber
1
Seperti yang saya katakan, Aktor TIDAK lebih kuat dalam apa yang dapat mereka hitung. Mereka (diklaim) lebih kuat dengan menampilkan "nondeterminisme tanpa batas" yang terkait dengan operasi bersamaan. Apa yang Anda maksudkan adalah hypercomputation , yang bukan subjek pertanyaan saya.
Adi Shavit
?! Hah! kekecewaan! tidak melihat apa pun tentang nondeterminisme tanpa batas dalam pertanyaan aktual Anda di atas. juga tidak membuat referensi langsung ke perhitungan dalam jawaban saya. yang memang merupakan salah satu bidang studi kelengkapan non-Turing, tetapi referensi yang saya berikan adalah satu lagi yang melibatkan "model interaktif"
vzn