Apa mesin Turing universal 2-negara nonkontroversial paling sederhana?

Saya ingin menyandikan mesin Turing sederhana dalam aturan permainan kartu. Saya ingin menjadikannya mesin Turing universal untuk membuktikan kelengkapan Turing.

Sejauh ini saya telah membuat status permainan yang mengkode mesin Turing 2-simbol, 3-simbol Alex Smith . Namun, tampaknya (diakui berdasarkan Wikipedia) bahwa ada beberapa kontroversi mengenai apakah (2, 3) mesin itu benar-benar universal.

Demi rigour, saya ingin bukti saya menampilkan UTM "non-kontroversial". Jadi pertanyaan saya adalah:

1. Apakah mesin (2,3) umumnya dianggap universal, non-universal, atau kontroversial? Saya tidak tahu di mana tempat yang memiliki reputasi baik untuk mencari jawabannya.

2. Jika mesin (2,3) tidak diterima secara luas sebagai universal, apa N terkecil sehingga mesin (2, N) diterima secara nonkontroversi sebagai universal?

Diedit untuk menambahkan: Ini juga akan berguna untuk mengetahui persyaratan apa pun untuk pita tak terbatas untuk mesin yang disebutkan, jika Anda kebetulan mengetahuinya. Tampaknya (2,3) mesin membutuhkan keadaan awal kaset yang non-periodik, yang akan agak sulit untuk disimulasikan dalam aturan permainan kartu.

Ada beberapa hasil baru sejak karya tersebut dikutip dalam jawaban sebelumnya. Survei ini menggambarkan keadaan terkini (lihat Gambar 1). Ukuran mesin Turing universal terkecil yang diketahui tergantung pada detail model dan berikut adalah dua hasil yang relevan dengan diskusi ini:

• Ada mesin universal standar 2-negara 18-simbol (Rogozhin 1996. TCS, 168 (2): 215-240). Di sini kita memiliki gagasan biasa tentang simbol kosong dalam satu atau kedua arah dari satu kaset.
• $r$$l$

Kedengarannya seperti (2,18) paling berguna untuk Anda.

$M$$w$$t$$M$$w$$t$

Angka tersebut menunjukkan mesin universal terkecil yang diketahui untuk berbagai model mesin Turing (diambil dari Neary, Woods SOFSEM 2012), referensi dapat ditemukan di sini .

Ini bukan jawaban nyata untuk pertanyaan Anda (saya tidak tahu banyak tentang (2,3) perdebatan mesin); tapi saya sarankan Anda kertas " mesin Turing Kecil dan kompetisi berang-berang sibuk umum ". Saya cepat membacanya beberapa waktu lalu, dan memiliki grafik yang bagus dengan garis batas antara 4 jenis TM kecil:

• decidable
• buka masalah seperti Collatz
• $3x + 1$
• universal

(mungkin beberapa hasil telah ditingkatkan).

Gagasan TM yang digunakan dalam makalah ini adalah definisi standar TM yang digunakan dalam makalah pada mesin Turing universal kecil:

... Mereka memiliki rekaman satu dimensi yang unik tanpa batas di kedua arah, dan kepala baca-tulis yang unik. Ada simbol kosong yang dilambangkan dengan 0. Awalnya, kata yang terbatas, input, ditulis pada kaset, sel-sel lain berisi simbol kosong, kepala membaca simbol paling kiri dari input, dan negara adalah keadaan awal. Pada setiap langkah, sesuai dengan kondisi mesin saat ini dan simbol dibaca oleh kepala, simbol dimodifikasi, kepala bergerak ke kiri atau ke kanan (dan tidak bisa tetap membaca sel yang sama), dan keadaan dimodifikasi. Perhitungan berhenti ketika kondisi penghentian khusus tercapai. ...

Dimungkinkan juga untuk mencapai universalitas dengan 7 negara dan 2 simbol, meskipun banyak dari keberatan yang sama berlaku (kondisi awal yang tidak seragam pada pita tak terbatas dan kondisi pemutusan yang tidak biasa). Lihat http://11011110.livejournal.com/104656.html dan http://www.complex-systems.com/abstracts/v15_i01_a01.html

Ini didasarkan pada simulasi otomat seluler Rule 110, yang dibuktikan universal oleh Matthew Cook, dan Cook juga menemukan simulasi 2-negara 5-simbol Rule 110, jika Anda terikat pada pembatasan bahwa hanya ada dua negara.

$S$$0\leq s < S$$C$$0\leq c< C$$2$$\text{L}$$\text{R}$$C+4SC$

Sepanjang waktu, hanya sel saat ini, atau dua sel yang terlibat dalam transisi, yang mungkin memiliki warna yang lebih baik: semua sel lain memiliki warna aslinya. Kami ingin mesin kami berperilaku sebagai berikut: periksa apa transisi yang benar untuk dilakukan, pindahkan informasi "kondisi sebenarnya" dari sel yang ingin kami tinggalkan ke sel target (ini melibatkan banyak bolak-balik), bersihkan sel yang kami tinggalkan (memberikan warna yang benar), ulangi.

$(c,s)$$\text{L}$$\text{R}$$(c_{\text{new}}, s_{\text{new}}, \text{emit})$$\text{L}$

$c$$\text{L}$$c$$(c,0, \text{L},\text{receive})$$\text{R}$

Berikut adalah transisi untuk mengimplementasikannya. Di hampir semua kasus, gerakkan ke arah yang ditentukan oleh kondisi saat ini, lalu balikkan keadaan

1. $c \to (c,0,\langle dir\rangle,\text{receive})$$\langle dir\rangle$

2. $(c,s) \to (c_{\text{new}},s_{\text{new}},\text{emit})$

3. $(c,s,\text{emit}) \to (c,s-1,\text{emit})$$s>0$

4. $(c,0,\text{emit}) \to c$

5. $(c,s, \langle dir\rangle, \text{receive}) \to (c, s+1, \langle dir\rangle, \text{receive})$$\langle dir\rangle$

6. $(c,s, \langle dir\rangle, \text{receive}) \to (c,s)$$\langle dir\rangle$

$C+3SC$

kecuali Anda dengan hati-hati mendefinisikan "tidak kontroversial" dalam beberapa cara teknis tidak ada jawaban yang tepat. inilah mesin kecil lain berdasarkan aturan 110 yang terbukti universal dalam pengertian tertentu tetapi pemahaman saya adalah bahwa ia membutuhkan formulasi kaset input periodik yang tak terbatas (dan juga ekstraksi pada akhirnya ketika mesin berhenti). belum melihat masalah rekaman "periodik vs non periodik" yang dijelaskan dalam literatur meskipun sudah dibahas pada misalnya milis matematika [Yayasan milis Matematika]

Bukti Turing-universalitas Alex Smith dari mesin Turing 3-simbol, 3-simbol yang diduga milik Wolfram jelas tidak kontroversial. Bukti universalitas yang diberikan (bukan mesin) membutuhkan pola tak terbatas pada pita Turing, dan pertanyaannya adalah apakah seseorang harus mengizinkan konfigurasi seperti itu (Anda dapat menganggap pita 'kosong' yang biasanya juga sebagai pola berulang simbol kosong yang tak terbatas). Kesimpulannya adalah selama konfigurasi pada pita mesin diperbaiki (yaitu tidak berubah setelah perhitungan Anda dimulai, dan tetap sama untuk perhitungan apa pun), maka perhitungan universal dilakukan oleh mesin Turing. Perhatikan bahwa ini BUKAN kontroversial untuk aturan Elementary Cellular Automaton 110 milik Wolfram yang terbukti universal oleh Wolfram dan Cook. Bukti universalitas aturan 110 juga memerlukan pola tak terbatas pada konfigurasi awal, yang berbeda di kedua sisi, dan karenanya memiliki sifat yang sama untuk mesin Turing 2-negara, 3-simbol. Kekhawatiran lain adalah bahwa mungkin pelonggaran persyaratan kondisi awal (kosong) akan membuat automata universal universal yang non-Turing diterima, seperti keadaan terbatas, terikat linier atau tekan automata untuk menyebutkan beberapa contoh, tetapi tidak dan menghormati hierarki Chomsky. Jadi jelas tidak kontroversial apakah mesin Turing 2-negara, 3-simbol itu universal, tetapi bukti universalitasnya memang membutuhkan variasi dari apa yang biasanya dianggap sebagai cotents dari tape mesin Turing biasa. Ini tidak berarti secara langsung, omong-omong, bahwa 2-negara,