Turing turing yang dapat dibalik?

Pertanyaan ini adalah tentang apakah ada tarpit Turing reversibel yang dikenal, di mana "reversibel" berarti dalam arti Axelsen dan Glück , dan "tarpit" adalah konsep yang jauh lebih informal (dan mungkin bukan pilihan kata yang sangat baik), tapi saya akan melakukan yang terbaik untuk menjelaskan apa yang saya maksud dengan itu.

Yang saya maksud dengan "tarpit"

Beberapa model perhitungan dirancang agar bermanfaat dalam beberapa cara. Yang lainnya kebetulan merupakan Turing yang lengkap dan tidak benar-benar memiliki sifat yang sangat berguna; ini dikenal sebagai "Turing tarpits". Contohnya termasuk bahasa Brainfuck , otomat seluler Rule 110 , dan bahasa Bitwise Cyclic Tag (yang saya suka karena sangat mudah diterapkan dan string biner apa pun adalah program yang valid).

Tidak ada definisi formal "Turing tarpit", tetapi untuk pertanyaan ini saya menggunakannya untuk berarti sistem yang cukup sederhana (dalam hal memiliki sejumlah kecil "aturan") yang "kebetulan" menjadi Turing lengkap, tanpa keadaan internalnya memiliki makna semantik yang jelas. Aspek yang paling penting untuk tujuan saya adalah kesederhanaan aturan, daripada kurangnya semantik yang jelas. Pada dasarnya kita berbicara tentang hal-hal yang pernah ditulis Stephen Wolfram pada buku yang sangat besar , walaupun dia tidak menggunakan kata "tarpit".

Yang saya maksud dengan "reversibel"

Saya tertarik pada perhitungan reversibel. Secara khusus, saya tertarik pada bahasa yang r-Turing lengkap, dalam arti Axelsen dan Glück , yang berarti mereka dapat menghitung setiap fungsi injeksi yang dapat dihitung, dan hanya dapat menghitung fungsi injeksi. Sekarang, ada banyak model perhitungan yang dapat dibalik dalam pengertian ini, seperti mesin Turing universal yang dapat dibalik , atau bahasa reversibel tingkat tinggi Janus . (Ada banyak contoh lain dalam literatur; ini adalah bidang penelitian yang aktif.)

Perlu dicatat bahwa definisi Axelsen dan Glück tentang kelengkapan r-Turing adalah pendekatan yang berbeda untuk komputasi reversibel daripada pendekatan yang biasa dilakukan oleh Bennett. Dalam pendekatan Bennett suatu sistem diperbolehkan untuk menghasilkan "data sampah" yang dibuang pada akhir perhitungan; dalam kondisi seperti itu, sistem reversibel dapat diselesaikan secara lengkap. Namun, dalam pendekatan Axelsen dan Glück, sistem tidak diperbolehkan untuk menghasilkan "data sampah" seperti itu, yang membatasi kelas masalah yang dapat dikomputasi. (Oleh karena itu, "r-Turing selesai" daripada "Turing lengkap".)

_{Catatan: kertas Axelsen dan Glück ada di belakang paywall. Ini sangat disayangkan - setahu saya saat ini tidak ada sumber daya yang tidak dibayar untuk masalah kelengkapan r-Turing. Saya akan mencoba untuk memulai halaman Wikipedia jika saya punya waktu, tetapi tidak ada janji.}

Apa yang saya cari

Contoh-contoh komputasi reversibel yang disebutkan di atas semuanya "sarat semantik". Ini adalah hal yang baik di sebagian besar konteks, tetapi itu berarti bahwa aturan yang diperlukan untuk memperbarui keadaan mereka pada setiap langkah waktu cukup kompleks. Saya mencari "tarpit" komputasi reversibel. Yaitu, sistem yang kurang lebih sewenang-wenang dengan aturan yang cukup sederhana yang "kebetulan" menjadi r-Turing bahasa lengkap. Saya tegaskan bahwa tidak ada definisi formal tentang apa yang saya cari, tetapi saya akan mengetahuinya ketika saya melihatnya, dan saya pikir itu adalah hal yang wajar untuk ditanyakan.

Ada beberapa hal yang saya tahu yang hampir sesuai dengan tagihan, tetapi tidak cukup. Ada beberapa automata seluler yang dapat dibalik yang telah terbukti Turing lengkap. Semut Langton (sejenis mesin Turing dua dimensi dengan fungsi transisi keadaan reversibel yang cukup sewenang-wenang dan cukup sederhana) juga Turing lengkap, asalkan kondisi awalnya dibiarkan mengandung pola berulang yang tak terbatas. Namun, dengan sistem ini tidak mudah untuk menentukan pemetaan dari negara mereka ke "output" sedemikian rupa sehingga tidak ada data sampah dibuang. Saya tertarik secara khusus pada sistem yang dapat dianggap sebagai mengambil input, melakukan beberapa urutan transformasi (reversibel) di atasnya, dan kemudian (jika mereka menghentikannya) mengembalikan beberapa output.

(Saya harap pertanyaan ini akan lebih mudah dijawab daripada yang terkait sebelumnya saya tentang yang setara dengan kalkulus lambda.)

"r-complete" tampaknya merupakan konsep yang relatif baru yang ditemukan oleh Axelsen dan Glück ~ 2011, mungkin tidak banyak dipertimbangkan oleh penulis lain, dan bertanya-tanya apakah ada bukti yang berbeda dari Turing lengkap.

Saya mengambil pertanyaan verbose & memutar ini untuk meminta pada dasarnya:

• sistem lengkap Turing sederhana
• reversibel

coba Turing-complete automata seluler yang dapat dibalik misalnya:

• Two-state, Reversible, Universal Cellular Automata Dalam Tiga Dimensi Miller / Fredkin

  Novel dua negara, Reversible Cellular Automata (RCA) dijelaskan. RCA tiga dimensi ini terbukti mampu melakukan komputasi universal. Selain itu, ditawarkan bukti bahwa RCA ini mampu membuat konstruksi universal.

• K. Imai dan K. Morita, Sebuah otomaton seluler dua-dimensi yang dapat dibalik tiga-dimensi yang bersifat komputasi-universal, Ilmu Komputer Teori 231 (2000), no. 2, 181–191.

  Abstrak: Automaton seluler reversibel (RCA) adalah otomat seluler (CA) yang fungsi globalnya bersifat injeksi dan setiap konfigurasi memiliki paling banyak satu pendahulunya. Margolus menunjukkan bahwa ada RCA 2-negara dua dimensi komputasi-universal. Tetapi RCA-nya memiliki tetangga yang tidak seragam, jadi Morita dan Ueno mengusulkan 16-negara penghitungan-universal RCA menggunakan dipartisi seluler automata (PCA). Karena PCA dapat dianggap sebagai subkelas dari CA standar, model mereka memiliki tetangga standar. Dalam tulisan ini, kami menunjukkan bahwa jumlah negara bagian model Morita dan Ueno dapat dikurangi. Untuk mengurangi jumlah status dari model mereka dengan pengawetan sifat isotropik dan pengawetan bit, kami menggunakan segitiga 3-tetangga, dan dengan demikian RCA 8-negara dapat dimungkinkan. Ini adalah negara RCA dua dimensi terkecil di bawah kondisi properti isotropik dalam kerangka PCA. Kami menunjukkan bahwa model kami dapat mensimulasikan elemen rangkaian dasar seperti kabel unit, elemen tunda, kabel persimpangan, gerbang sakelar, dan gerbang sakelar terbalik, dan dimungkinkan untuk membangun gerbang Fredkin dengan menggabungkan elemen-elemen ini. Karena gerbang Fredkin dikenal sebagai gerbang logika universal, model kami memiliki komputasi-universalitas.

itu ditemukan sebagai referensi dalam survei CA ini yang mungkin memiliki petunjuk bermanfaat lainnya pada penyelidikan (mis. lihat bagian 7, Reversibilitas dan Universalitas). (pada 17 pgs & 86 referensi judulnya hampir ironis.)

UNIVERSALITAS DALAM SURVEI CELLULAR AUTOMATA A (PENDEK) Ollinger