Bagaimana aturan 110 Turing selesai?

Saya telah membaca halaman wikipedia untuk aturan 110 dalam automata seluler, dan saya kurang lebih tahu cara kerjanya (seperangkat aturan menentukan di mana menggambar 1 atau 0 berikutnya).

Saya baru saja membaca bahwa Turing sudah lengkap, tetapi saya bahkan tidak bisa mengerti bagaimana Anda 'memprogram' dalam 'aturan 110'?

Universalitas adalah gagasan yang agak informal. Artinya kira-kira adalah bahwa untuk setiap fungsi yang dapat dihitung ada "program" P dalam model sehingga "menjalankan" P pada input apa pun x selalu "berhenti", dan "mengeluarkan" jawaban yang benar. (Perhatikan bahwa mesin Turing tidak membuat tampilan di sini: mereka hanyalah salah satu contoh model komputasi universal.)$f$$P$$P$$x$

Kata-kata yang dikutip adalah kata-kata yang perlu didefinisikan. Untuk mesin Turing:

• Suatu program ditentukan sebagai daftar negara, alfabet tape, keadaan awal, keadaan akhir, dan transisi.
• Menjalankan mesin Turing pada input x berarti kita menginisialisasi rekaman dengan pengkodean x dan menjalankan mesin T pada rekaman ini sesuai dengan aturan yang biasa.$T$ $x$$x$$T$
• Mesin Turing berhenti jika mencapai kondisi akhir. (Ada beberapa varian di sini.)
• Apa mesin Turing output (jika menghentikan) adalah isi rekaman itu.

Aturan 110, sebagai model perhitungan, perlu didefinisikan secara formal dengan cara yang sama. Definisi masuk akal jika seseorang dapat mensimulasikan komputasi model komputasi, dalam arti berikut: ada fungsi yang dapat dihitung sedemikian rupa sehingga untuk setiap program P dan input x (keduanya dikodekan sebagai bilangan asli), S ( P , x ) berhenti iff P berhenti pada x , dan jika S ( p , x ) berhenti maka outputnya identik dengan output P pada x .$S$$P$$x$$S(P,x)$$P$$x$$S(p,x)$$P$$x$

Jika Anda ingin tahu tentang pengaturan tertentu dari Aturan 110 sebagai sistem komputasi, saya sarankan Anda melihat kertas Matthew Cook yang membuktikan universalitas Peraturan 110 (atau lebih tepatnya, sistem komputasi yang dibangun berdasarkan Aturan 110).

Adapun aturan lain, seperti Aturan 30 dan Aturan 90, kita tidak tahu bahwa mereka tidak universal. Mungkin ada sistem komputasi meyakinkan yang dibangun di sekitar mereka yang bersifat universal, tetapi kami tidak menyadarinya.

Dari bukti Matius:

Pendekatan yang diambil di sini bukan untuk merancang otomat seluler baru, tetapi untuk mengambil yang paling sederhana yang secara alami menunjukkan perilaku kompleks, dan melihat apakah kita dapat menemukan dalam perilaku kompleks cara untuk membuatnya melakukan apa yang kita inginkan. Kami tidak akan menyibukkan diri kami secara langsung dengan tabel pencarian yang diberikan di atas, tetapi sebaliknya kami akan melihat perilaku yang secara alami ditunjukkan oleh tindakan otomat dari waktu ke waktu.

Penulis pertama kali memulai dengan membuktikan bahwa "sistem tag" yang menghilangkan 2 simbol pada setiap langkah bersifat universal dengan menyusun program mesin turing 2-kondisi. Setelah itu, ia membuktikan bahwa sistem glider memang dapat menerapkan sistem tag. Ini adalah proses langkah demi langkah. Kemudian, ia mempelajari waktu ruang CA-110 untuk menemukan glider dan mengaitkannya dengan sistem glider dengan benar.

Sekarang, untuk pertanyaan Anda: bagaimana Anda 'memprogram' dalam 'aturan 110'?

1. Cari mesin turing 2-keadaan paling sederhana dan temukan kaset-kaset operasi dasar ATAU, DAN, XOR, BUKAN .

2. Kompilasi mereka ke sistem tag.

3. Kompilasi implementasi sistem tag ke dalam implementasi glider.

4. Menyesuaikannya dengan CA-110 glider dengan benar dan Anda memiliki operasi dasar dalam automata seluler.

$1+1=2$

Di samping catatan. Glider adalah struktur yang sangat istimewa. Operasi akan dilihat sebagai partikel yang bergerak dan bertabrakan (glider), menghasilkan output yang berbeda tergantung pada bagaimana glider ini memulai atau bertabrakan.