Ubin Wang (domino) diciptakan oleh Hao Wang pada tahun 1961 untuk masalah matematika, tetapi banyak digunakan dalam game untuk membuat grafis ubin. Berkat mereka, hasilnya tidak terlihat berulang, baik dalam tekstur 2D dan dalam model 3D dengan ubin.
Tampaknya ubin Van juga mampu mengeksekusi mesin Turing, dan karenanya, Turing-complete, yang berarti mereka dapat menjalankan program apa pun.
Ini adalah pernyataan yang luar biasa dan tidak bisa dipahami, jadi dalam posting ini saya akan menyelidiki sedikit masalah ini.
Secara singkat tentang Van Tiles
Ubin van adalah ubin persegi panjang di mana masing-masing wajah hanya dapat sesuai dengan wajah tertentu lainnya, tetapi untuk wajah tertentu ada beberapa ubin yang mungkin bisa sesuai dengan wajah itu. Dengan mencocokkan wajah, maksud saya mereka terhubung dengan mulus tanpa membuat artefak visual atau tanda-tanda jahitan di antara ubin.
Properti ini berguna untuk grafik, karena memungkinkan Anda untuk membuat grafik ubin yang mulus, tetapi konfigurasi lokasi ubin dapat sepenuhnya acak, asalkan semua wajah kompatibel satu sama lain. Hasilnya adalah grafik ubin, yang sama sekali tidak seperti yang berulang, karena pola visual menjadi jauh lebih terlihat daripada grafik ubin tradisional.
Contoh grafik, informasi lebih rinci, dan tautan ke Shadertoy dapat ditemukan di sini:
Wang Tiling .
Ini adalah contoh yang saya buat. Grafik saya adalah "programmer seni", tapi saya harap idenya jelas. Gambar itu terdiri dari 16 ubin, dan untuk setiap wajah ada dua jenis wajah yang berbeda.
Secara singkat tentang mesin Turing
Mesin Turing diciptakan pada tahun 1936 oleh Alan Turing sebagai komputer umum, yang terbukti dapat menjalankan algoritma apa pun.
Mesin Turing terdiri dari beberapa komponen utama: kaset memori, kepala baca / tulis, dan mesin negara.
Kaset memori memiliki panjang tak terbatas, yaitu, ia memiliki kapasitas penyimpanan tak terbatas, dan pada awalnya itu diinisialisasi dengan nol saja.
Kepala baca / tulis dimulai dari posisi tertentu dari kaset dan dapat membaca / menulis nilai-nilai, dan juga bergerak ke kiri dan ke kanan sepanjang rekaman itu.
Mesin negara mengontrol kepala baca / tulis.
Mesin negara tahu keadaan apa itu, dan memiliki aturan tentang apa yang harus dilakukan di setiap negara bagian ketika membaca nilai dari rekaman itu.
Misalnya, di negara A, jika 0 dibaca dari kaset, maka aturannya adalah menulis 1 ke posisi rekaman saat itu, memindahkan kepala baca / tulis ke kanan, atau pergi ke negara B. Negara B dapat memiliki logika yang sama sekali berbeda dan dapat melakukan transisi kembali ke negara A, atau tetap di negara B, atau pindah ke negara yang sama sekali berbeda.
Dengan menggunakan logika transisi antar negara yang begitu sederhana, algoritma komputer apa pun dapat dijalankan.
Mesin Turing mungkin juga memiliki "Halt State," yang berarti bahwa program telah menyelesaikan eksekusi dan responsnya telah dihitung.
Mencari beberapa program. dapat dengan mudah dilihat. bahwa seiring berjalannya waktu, mereka akan berakhir atau akan berada dalam lingkaran yang tak terbatas dan tidak akan pernah berhenti. Beberapa program terletak di antara mereka, mereka kompleks dan tidak begitu mudah untuk menentukan apakah mereka akan pernah berhenti. Turing membuktikan bahwa tidak ada solusi umum untuk menentukan apakah mesin Turing akan berhenti (ini adalah program komputer), dan ini disebut
masalah berhenti . Secara umum, satu-satunya cara untuk mengetahui apakah suatu program berhenti adalah menunggu. Faktanya, dalam kasus umum, jawaban untuk pertanyaan ini adalah "ya" atau "belum", namun, dalam kasus banyak program tertentu, Anda dapat melihat bahwa setelah peluncuran mereka akan berakhir seiring waktu.
Perhitungan Wang Tile
Ternyata ubin Wang dapat mensimulasikan mesin Turing, yaitu, mereka Turing-lengkap, yang berarti bahwa mereka dapat menjalankan algoritma komputer apa pun.
Untuk mewujudkan hal ini, kita memerlukan kolom ubin Van yang menunjukkan keadaan mesin Turing pada titik waktu tertentu, mulai dari waktu 0 di kolom paling kiri. Kami akan menempatkan ubin di kolom di sebelah kanan dengan semua aturan wajah, dan kemudian membuat kolom di sebelah kanannya, dan seterusnya, sampai program berakhir (atau kami akan melakukan ini selamanya jika tidak berakhir). Jika Anda memilih set ubin yang benar, maka memeriksa kepatuhan dengan aturan wajah dalam proses mengatur ubin akan cukup untuk menyelesaikan mesin Turing.
Mari kita lihat contoh sederhana yang memiliki aturan logika mesin negara berikut:
- Ketika mesin dalam keadaan A, maka dalam kasus membaca 0, kita menulis 1, memindahkan kepala baca / tulis ke bawah dan pergi ke negara B.
- Ketika mesin dalam keadaan A, dalam kasus membaca 1, program berhenti (beralih ke keadaan akhir).
- Ketika mesin dalam keadaan B, dalam kasus membaca 0, kita menulis 1, naikkan kepala baca-tulis dan lanjutkan ke keadaan A.
- Ketika mesin dalam keadaan B, dalam kasus membaca 1, program berhenti (masuk ke keadaan akhir)
Tape drive
Pertama-tama, kita membutuhkan penyimpanan permanen untuk rekaman itu. Untuk melakukan ini, kita perlu dua ubin berikut:
Untuk menguji pekerjaan mereka, kami dapat menyiapkan segmen pita dengan beberapa nilai (membuat kolom ubin Van) dan memastikan bahwa ubin Van yang cocok yang terletak di sebelah kolom awal adalah ubin yang mentransfer nilai 0 dan 1 ke depan dalam waktu tanpa mengubah mereka.
Dalam diagram di bawah ini, kami menginisialisasi rekaman dengan nilai 0101 di kolom paling kiri (waktu 0). Hanya memiliki ubin dengan wajah yang kompatibel, kita melihat bahwa nilai-nilai dalam memori disimpan selamanya. Kami telah mengimplementasikan drive memori!
Kami akan mulai menunjukkan contoh kami dengan memori yang diinisialisasi ke 0, dan gambar di atas hanya menunjukkan kegigihan memori.
Mesin kepala baca-tulis
Kepala baca / tulis mesin Turing disajikan sebagai bagian dari informasi wajah. Jadi, selain menyimpan wajah 0 atau 1, jika kepala baca / tulis ada di dalamnya, maka ia juga menyimpan keadaan mesin negara.
Dalam contoh kami, dua status digunakan (tidak termasuk status akhir): A dan B. Jika 1 dibaca, maka di salah satu negara bagian (A atau B) program berakhir.
Untuk menangani ini, kita perlu ubin berikut:
Sekarang kita memiliki aturan untuk beralih ke kondisi akhir (aturan 2 dan 4), kita perlu memahami bagaimana menerapkan aturan yang mengontrol peralihan dari satu kondisi ke kondisi lain (aturan 1 dan 3).
Memindahkan kepala baca / tulis
Aturan 1 menyatakan bahwa jika kita berada dalam keadaan A dan membaca 0, kita harus menulis 1, memindahkan kepala baca / tulis ke bawah dan pergi ke negara B.
Kita perlu ubin ini untuk membaca 0 dalam keadaan A, untuk menulis 1 sebagai keluaran, dan memerintahkan ubin di bawah ini untuk masuk ke keadaan B.
Ubin di bawah yang saat ini dapat memiliki nilai 0 atau 1; tanpa mengetahui nilai tertentu, kita harus menyimpannya, tetapi menerima kepala baca / tulis dan dalam keadaan B. Untuk ini, kita perlu dua ubin - satu untuk 0 pada rekaman di posisi ini, yang lain untuk 1 pada pita.
Aturan 3 menyatakan bahwa jika kita berada di negara B dan membaca 0, kita harus menulis 1, memindahkan kepala baca-tulis ke atas dan pergi ke negara A.
Untuk melakukan ini, kita memerlukan konstruksi yang mirip dengan konstruksi untuk aturan 1, tetapi kita tidak bergerak turun, tetapi naik. Tiga ubin berikut akan memberikan hasil yang diinginkan:
Ubin Kolom Awal
Kami akan melihat batas-batas area simulasi seolah-olah mereka memiliki wajah "x".
Ini berarti bahwa untuk membuat kolom awal (mesin Turing pada waktu 0) kita perlu dua ubin khusus. Satu ubin diperlukan untuk menyimpan nilai 0 pada kaset, yang menginisialisasi rekaman itu, dan ubin lain - untuk menyimpan posisi kepala baca / tulis dalam keadaan A, yang merupakan keadaan awal kami.
Dua ubin ini adalah:
Set ubin siap
Ini adalah 12 ubin lengkap yang akan kita gunakan:
Simulasi penuh
Berikut adalah desain asli dari mesin Turing kami pada waktu 0. Perhatikan bahwa ini adalah salah satu kondisi awal yang mungkin, tetapi ini adalah kondisi yang kami pilih. Kami tidak memberikan kesempatan untuk memilih dari mana kepala baca / tulis dimulai, dan kehadirannya juga. Jika kita hanya mengikuti aturan wajah, maka kita bisa mendapatkan 4 atau 0 kepala baca-tulis, atau nomor apa pun di antara mereka.
Dari sini, untuk membuat kolom kedua, kita mulai dari atas dan bergerak ke bawah, memilih ubin yang cocok dengan batasan wajah yang disentuhnya. Pada langkah pertama ini, kepala membaca 0, menulis 1, bergerak ke bawah dan pergi ke keadaan B.
Inilah langkah kedua, di mana kepala membaca 0, menulis 1, bergerak ke atas dan masuk ke keadaan A.
Berikut ini adalah langkah terakhir di mana kepala membaca 1 dan memasuki keadaan akhir, menunjukkan bahwa program selesai.
Program berakhir dan memberi kami nilai output 0110, atau 6. Nilai-nilai output ini tidak terlalu signifikan, tetapi program lain dapat menghasilkan output yang signifikan. Sebagai contoh, kita dapat memaksa mesin Turing untuk menambahkan dua angka, dan output akan menjadi jumlah dari dua angka ini.
Detail penting
Di sini kita harus menyebutkan detail penting yang tidak kita pertimbangkan di atas, dan yang tidak disebutkan dalam sebagian besar penjelasan mesin Turing pada ubin Van.
Ketika menempatkan ubin kedua untuk waktu 2, satu-satunya batasan pada wajah adalah bahwa ubin harus memiliki x di atas dan 1 di sebelah kiri. Bahkan, karena ini, situasinya menjadi ambigu, karena tidak jelas mana dari dua ubin yang ditunjukkan di bawah ini yang harus dipilih.
Lalu bagaimana kita memilih yang benar?
Jawabannya adalah kita hanya membuat asumsi dan memilih salah satunya. Jika dalam kasus ini ubin yang salah dipilih, maka ketika kita beralih ke ubin berikutnya, kita akan mencari ubin dengan x di atas dan B0 di sebelah kiri. Ubin semacam itu tidak ada, jadi kami tidak dapat menempatkan ubin tersebut. Ketika ini terjadi, kita perlu kembali ke ubin terakhir dan mencoba salah satu opsi lain.
Sayangnya, ketika mensimulasikan mesin Turing menggunakan ubin Wang, secara harfiah ada proses coba-coba, tetapi setidaknya itu cukup mudah dikelola. Ini benar-benar menyulitkan perhitungan sedikit di pixel shader (atau di perangkat lain dengan paralelisme tinggi), tetapi biayanya tidak lebih.
Kesimpulan dan tautan
Beberapa tautan di bawah ini membahas ubin Wang dan mesin Turing, tetapi diskusi tersebut tampaknya tidak sepenuhnya mematuhi mesin Turing. Sebagai contoh, Anda mungkin memperhatikan bahwa dalam beberapa contoh data diizinkan untuk mengembalikan "waktu" - ketika program berakhir, jawabannya ada pada rekaman pada waktu 0 dari mesin Turing, meskipun fakta bahwa data ini tidak ada pada waktu 0. Ini menunjukkan bahwa ubin Wang dapat melakukan perhitungan sendiri, tidak hanya mensimulasikan mesin Turing, tapi saya tidak tahu persis apa teknik ini akan disebut.
Selain itu, jika Anda tertarik untuk mengetahui apa yang berguna dalam komputasi menggunakan ubin Wang, maka secara pribadi saya tidak bisa membayangkan kasus-kasus aplikasi praktis mereka. Namun, para ilmuwan tampaknya telah menemukan bahwa DNA dapat bertindak dalam cara yang sama seperti ubin Van dalam arti bahwa koneksi dibuat hanya antara wajah yang kompatibel. Berkat ini, perhitungan berbasis DNA sekarang sedang diteliti berdasarkan proses komputasi menggunakan ubin Wang. Topik yang cukup menarik!
Berikut adalah implementasi penghitungan bilangan prima menggunakan ubin Wang di Shadertoy di pixel shader WebGL:
Shadertoy: WangTiles: PrimeGeneratorBerikut adalah beberapa video hebat tentang mobil Turing dan masalah berhenti:
Mesin Turing Dijelaskan - ComputerphileTuring & Masalah Pemutusan - ComputerphileDan inilah beberapa tautan lagi:
Komputasi dengan ubinWikipedia: Ubin vanWang Tiles dan Mesin TuringWang Tiles - 1Inilah beberapa artikel ilmiah:
Komputasi dengan ubinKompabilitas tilings