Apakah versi gim Conway tentang kehidupan mendukung komputasi universal?

30

Mengutip Wikipedia , "[Permainan Kehidupan Conway] memiliki kekuatan mesin Turing universal: yaitu, apa pun yang dapat dihitung secara algoritmik dapat dihitung dalam Permainan Kehidupan Conway."

Apakah hasil seperti itu meluas ke versi berisik dari Conway's Game of Life? Versi paling sederhana adalah bahwa setelah setiap putaran setiap sel hidup mati dengan probabilitas kecil dan setiap sel mati menjadi hidup dengan probabilitas kecil s (secara independen).ts

Kemungkinan lain adalah mempertimbangkan varian probabilistik berikut dari aturan permainan itu sendiri.

  • Setiap sel hidup dengan kurang dari dua tetangga hidup mati dengan probabilitas .1−t
  • Setiap sel hidup dengan dua atau tiga tetangga hidup hidup dengan probabilitas ke generasi berikutnya.1−t
  • Setiap sel hidup dengan lebih dari tiga tetangga hidup mati dengan probabilitas .1−t
  • Setiap sel mati dengan tiga tetangga langsung menjadi sel hidup dengan probabilitas .1−t

Pertanyaan: Apakah versi Game yang berisik ini masih mendukung perhitungan universal? Jika tidak, apa yang bisa dikatakan tentang "kekuatan komputasi" mereka?

Informasi terkait tentang kekuatan komputasi automata seluler dan versi bising automata seluler juga akan sangat dihargai.

(Pertanyaan ini dikembangkan dari pertanyaan ini pada MathOverflow. Jawaban Vincent Beffara pada MO memberikan referensi yang menarik untuk hasil terkait pada aspek komputasi automata seluler yang bising.)

cc.complexity-theory pr.probability cellular-automata fault-tolerance Gil Kalai
sumber
2
@ ay 1) tidak, ini bukan "pertanyaan sebenarnya," ini adalah pertanyaan yang sama sekali berbeda; Pertanyaan Gil adalah tentang kekokohan model komputasi sederhana terhadap noise, bukan tentang kekuatan keacakan; 2) TM dengan pita acak tidak lebih kuat dari TM deterministik, lihat jawaban ini: cstheory.stackexchange.com/a/1415/4896
Sasho Nikolov
2
Pertanyaan sebenarnya di sini adalah apakah versi stokastik / berisik dari "Game of Life" masih mendukung perhitungan. (Jika versi ini mendukung perhitungan dalam P, maka kekuatan mereka dapat sampai ke BPP.) Ada kemungkinan bahwa kekuatan komputasi dari versi stokastik permainan kehidupan ini jauh lebih rendah.
Gil Kalai
3
Mungkin saya menyatakan yang sudah jelas, tetapi Anda hanya dapat menduplikasi konfigurasi cukup kali untuk menjamin dengan probabilitas tinggi bahwa versi konfigurasi bahkan tidak memiliki satu sel pun terbalik. Keyakinan pribadi saya adalah bahwa kita dapat melakukan banyak, jauh lebih baik, tetapi setidaknya itu adalah batas bawah yang sederhana.
user834
4
Saya tidak yakin pertanyaannya jelas. Misalkan . Tampak bagi saya bahwa Anda mungkin dapat menemukan komputer yang menangani semua kesalahan satu-bit dalam "Game of Life", memberikan Anda perhitungan yang toleran terhadap kesalahan kecuali Anda secara spontan mendapatkan blok kesalahan besar sekaligus. Tapi saya tidak berpikir apa pun bisa kuat terhadap semua kesalahan. Sebagai contoh, misalkan kesalahan secara spontan membuat musuh jahat yang ditentukan untuk mengganggu perhitungan. Anda mungkin dapat menunjukkan perhitungan Anda berhasil dengan probabilitas > 1 - 10 - 9 tetapi gagal dengan probabilitas > 10 - 10.000 . Apakah ini masuk hitungan?t=10−9>1−10−9>10−10000
Peter Shor
2
Peter, jika perhitungan Anda berhasil dengan probabilitas 2/3, saya senang.
Gil Kalai

Jawaban:

8

Berikut adalah beberapa referensi "terdekat terbaik", untuk apa nilainya. Tampaknya cara untuk menjawab pertanyaan ini adalah menguranginya menjadi pertanyaan tentang "mesin Turing yang berisik", yang telah dipelajari (agak baru), dan yang tampaknya merupakan bidang literatur terdekat yang relevan. Jawaban dasar / umum / masuk akal adalah bahwa jika TM dapat menolak / mengoreksi kebisingan (seperti yang ditunjukkan dalam referensi ini), sangat mungkin CA juga, dalam beberapa batasan / ambang batas.

Pertanyaan tentang bagaimana mengurangi "bising CA" menjadi "bising TM" (dan sebaliknya) lebih terbuka. Ini mungkin tidak sulit tetapi tampaknya tidak ada penelitian yang dipublikasikan di daerah tersebut. Masalah lain adalah bahwa TM berisik adalah model baru dan oleh karena itu mungkin ada beberapa (alami?) Cara untuk mewakili TM berisik. Sebagai contoh, makalah-makalah berikut melihat gangguan dalam fungsi transisi negara, tetapi model alami lainnya adalah gangguan pada simbol rekaman (yang terakhir lebih terhubung ke CA bising?). Mungkin ada beberapa hubungan di antara keduanya.

  • Mesin Turing Fault-tolerant oleh Ilir Capuni, 2012 (tesis PhD)

    Mesin Turing adalah model komputasi universal yang paling banyak dipelajari. Tesis ini mempelajari pertanyaan apakah ada mesin Turing yang dapat menghitung dengan andal bahkan ketika pelanggaran fungsi transisinya terjadi secara independen satu sama lain dengan beberapa kemungkinan kecil.

    Dalam tesis ini, kami membuktikan keberadaan mesin Turing yang dengan overhead polinom dapat mensimulasikan mesin Turing lainnya, bahkan ketika mengalami kesalahan jenis di atas, dengan demikian menjawab pertanyaan yang terbuka selama 25 tahun.

  • Mesin Turing Menolak Bursts Of Faults yang Terisolasi oleh Ilir Capuni dan Peter Gacs, 2012
  • Noisy Turing Machines oleh Eugene Asarin dan Pieter Collins, 2005
(Pertanyaan lain: mungkinkah ada hubungan antara TM yang berisik dan probabilistic Turing Machines ?)

ay
sumber
7

Gil bertanya apakah GL lupa segalanya tentang konfigurasi awalnya dalam waktu yang independen dari ukuran, ketika setiap sel "tidak mematuhi" fungsi transisi secara independen dari sel lain dengan beberapa kemungkinan kecil.

Sepengetahuan saya, ini tidak dikenal untuk GL. Ini adalah pertanyaan yang sangat menarik. Jika ia dapat menahan kebisingan, maka ia harus mempertahankan keuniversalannya.

Gambaran singkat dari keadaan seni adalah sebagai berikut.

  1. Aturan Toom dapat menyimpan sedikit kesalahan selamanya yang terjadi secara independen satu sama lain dengan beberapa probabilitas kecil.
  2. Dipercayai secara luas (dugaan laju positif) bahwa semua 1 dim CA adalah ergodik sampai P. Gacs membangun CA multi-skala yang dapat mensimulasikan CA lainnya dengan overhead yang moderat bahkan ketika mengalami kebisingan yang disebutkan sebelumnya.
  3. Pertanyaan jika G (acs) K (urdiumov) L (evin) aturan dapat menghemat sedikit pun selamanya di hadapan kebisingan di atas masih terbuka. Taman Kihong - seorang siswa Gacs --- menunjukkan bahwa itu tidak akan terjadi, ketika kebisingannya bias.
  4. Ketika pekerjaan di 2 diterbitkan, M. Blum bertanya apakah TM dapat meneruskan perhitungannya jika pada setiap langkah, transisi tidak dilakukan sesuai dengan fungsi transisi dengan beberapa probabilitas kecil secara independen dari langkah-langkah lain, dengan asumsi bahwa informasi yang disimpan di pita yang jauh dari kepala tidak membusuk. Jawaban positif diberikan oleh I. Capuni (siswa lain dari Gacs) pada tahun 2012.
pengguna8719
sumber
"Jika tidak ergodik, maka itu akan menjaga keuniversalannya" ... apakah Anda punya bukti untuk pernyataan ini? Apakah ini teorema? Di mana itu terbukti? Saya percaya bahwa karya Gacs menunjukkan bahwa ini benar dalam setidaknya satu kasus, tapi saya tidak melihat bagaimana itu terbukti untuk permainan Conway of Life.
Peter Shor
Terima kasih telah menunjukkan. Ini bukan teorema tetapi pertanyaan terbuka yang menarik. Tidak menjadi ergodik sepertinya terlalu sedikit untuk meminta pernyataan yang kuat.
user8719
3

Sebagai permulaan, perlu diingat bahwa penelitian di Game of Life Conway masih berlangsung dan perkembangan di masa depan dapat memberikan solusi yang jauh lebih rumit.

Nah sekarang. Cukup menarik, ini adalah topik yang sebenarnya sama dengan biologi dan fisika kuantum seperti halnya dengan ilmu komputer tradisional. Pertanyaan yang menjadi akar masalah adalah apakah perangkat apa pun dapat secara efektif menolak perubahan acak pada kondisinya. Jawaban yang jelas dan sederhana adalah bahwa tidak mungkin membuat mesin seperti itu dengan sempurnatahan terhadap perubahan acak tersebut. Tentu saja, ini benar dalam banyak cara yang sama bahwa mekanika kuantum dapat menyebabkan peristiwa yang tampaknya mustahil. Apa yang mencegah peristiwa-peristiwa ini terjadi (membuat kebanyakan orang menyatakan hal itu sangat mustahil) adalah kemungkinan kecil yang luar biasa dari peristiwa semacam itu terjadi. Probabilitas yang dibuat sangat kecil oleh perbedaan skala besar antara tingkat kuantum dan tingkat manusia. Demikian pula mungkin untuk membuat mesin negara yang tahan terhadap perubahan acak tingkat kecil hanya dengan membuatnya begitu besar dan berlebihan sehingga setiap "perubahan" yang diperhatikan secara efektif nol, tetapi asumsinya adalah bahwa ini bukan tujuannya. Dengan asumsi itu, ini dapat dicapai dengan cara yang sama bahwa hewan dan tumbuhan tahan terhadap radiasi atau kerusakan fisik.

Pertanyaannya kemudian mungkin bukan bagaimana mencegah gangguan tingkat rendah dari melakukan terlalu banyak kerusakan, tetapi bagaimana memulihkan dari kerusakan sebanyak mungkin. Di sinilah biologi menjadi relevan. Hewan dan tumbuhan sebenarnya memiliki kemampuan ini pada tingkat sel. (Harap dicatat: Saya berbicara tentang sel dalam arti biologis dalam jawaban ini) Sekarang, dalam permainan kehidupan Conway, gagasan membangun perangkat komputer pada skala sel tunggal memang menarik (bagaimanapun, membuat kreasi seperti itu jauh lebih kecil dan lebih efisien), tetapi sementara kita dapat membangun komputer yang dapat mereproduksi sendiri ( lihat Gemini ), ini mengabaikan fakta bahwa objek konstruktor itu sendiri dapat menjadi rusak oleh gangguan.

Cara lain, yang lebih tangguh, yang dapat saya lihat untuk menyelesaikan ini adalah membangun komputer dari bagian-bagian yang berlebihan yang dapat direproduksi sendiri (pikirkan sel biologis) yang melakukan operasi, bereproduksi, dan diganti.

Pada titik ini kita bisa melihat paralel dunia nyata yang menarik. Gangguan tingkat rendah ini mirip dengan efek radiasi. Ini paling dihargai ketika Anda mempertimbangkan jenis kerusakan yang dapat dilakukan pada automata seluler Anda. Sangat mudah untuk memicu kegagalan kaskade atau "kematian" sel dalam Conway's Game of Life, sama seperti apa yang terjadi pada banyak sel yang terpapar radiasi. Tetapi ada kemungkinan mutasi terburuk, menciptakan sel "kanker" yang terus mereproduksi salinan yang salah dari dirinya sendiri yang tidak membantu dalam proses komputasi, atau menghasilkan hasil yang salah.

Seperti yang telah saya katakan, mustahil untuk membangun sistem yang sepenuhnya aman, Anda hanya dapat membuatnya semakin kecil kemungkinannya untuk mengkompromikan seluruh sistem. Tentu saja, pertanyaan mendasar di sini adalah "apakah simulasi probabilistik itu sendiri sudah selesai" yang telah diputuskan untuk menjadi kenyataan . Saya akan menjawab pertanyaan mendasar itu pada awalnya, kecuali bahwa itu bukan yang Anda tanyakan.

Hawkwing
sumber
Wow! Terima kasih untuk drive-by-downvote! Bagaimanapun, saya telah merevisi posting saya, menambahkan beberapa informasi dan sumber. Maaf saya tidak punya waktu untuk melakukan itu ketika saya pertama kali memposting ini. Saya dapat memodifikasi jawaban ini lebih jauh agar sesuai dengan standar komunitas, jika bukan karena fakta bahwa tidak ada alasan untuk downvote.
Hawkwing
5
Sebagai non-pemilih, saya tidak melihat bagaimana ini menjawab pertanyaan Gil. Anda menjawab pertanyaan apakah "perangkat apa pun dapat secara efektif menolak perubahan acak pada kondisinya", yang bukan itu yang ditanyakan Gil.
András Salamon
Terima kasih (tanpa sarkastis kali ini) atas komentarnya, András Salamon. Saya akan memilih itu berguna sendiri, tetapi saya masih pengguna baru di situs melimpah ini. Bagaimanapun, maaf jawaban saya sepertinya di luar topik. Saya mungkin menjawab pertanyaan itu lebih longgar daripada yang saya maksudkan, tetapi saya merasa jawaban saya benar-benar menanggapi pertanyaan awal dengan menjawab pertanyaan yang sama dan kemudian menarik paralel antara keduanya. Apakah ini mungkin terlalu bundaran cara menjawab?
Hawkwing
0

Saya diingatkan tentang xkcd 505: A Bunch of Rocks .

Komputer dunia nyata apa pun tunduk pada tingkat kebisingan tertentu. Simulasi komputer universal dalam semesta Life Conway tak terbatas yang ideal akan memiliki waktu rata-rata di antara kegagalan yang bergantung pada detail rekayasa desainnya. Ini akan menghitung secara andal untuk periode yang dapat dihitung secara probabilistik, tidak dapat dipercaya untuk periode akumulasi kesalahan, dan kemudian tidak sama sekali .

Saya mengharapkan logika fuzzy atau model superposisi kuantum untuk menunjukkan dengan jelas keandalan apa yang diharapkan dari konstruksi tertentu. Seseorang mungkin ingin mensimulasikan output yang diharapkan dari berbagai komponen, daripada mengulangi semua sel mereka, sampai taraf tertentu mereka dapat diisolasi satu sama lain. Seseorang mungkin dapat mengukur gangguan yang diharapkan dari komponen yang gagal. Algoritme genetik harus menjadi cara terbaik untuk mengembangkan komponen fault- {mentolerir, menolak, mengoreksi} dengan MTBF sebesar yang diinginkan untuk distribusi noise yang diberikan.

pengguna130144
sumber
(Pemungutan suara misterius di sini) Jawaban kuantitatif akan sangat spekulatif. Tidak mungkin ada jawaban yang lebih tepat daripada "ya, kondisional" tanpa eksperimen ekstensif pada beberapa implementasi UTM yang dipilih. Sebuah yang normal komputer di lingkungan radiasi tinggi masih praktis UTM, jika hanya sebentar.
user130144