Untuk merayakan ulang tahun Alan Turing, Google menerbitkan doodle yang menunjukkan mesin. Mesin seperti apa doodle itu? Bisakah itu mengekspresikan bahasa Lengkap Turing?
Ada perbedaan yang jelas dengan mesin turing klasik: pita terbatas, kendala dalam bagaimana negara dapat dihubungkan, ...
Orat-oret masih tersedia di sini
(Tampilan di kanan atas menunjukkan output yang diharapkan.)
Kaset di tengah dibagi menjadi kotak yang dapat menampung kosong, nol atau satu. Kepala diposisikan di atas salah satu kotak dan digunakan untuk membaca dan menulis.
Di bawah rekaman itu Anda dapat melihat panah hijau yang dapat Anda klik untuk memulai mesin. Ada dua garis lingkaran di sebelahnya, beberapa di antaranya terhubung. Saya akan memanggil mereka "negara".
Setelah mesin dimulai, status pertama di sebelah kanan tombol hijau menyala, lalu yang berikutnya ke kanan, dan seterusnya ... Setiap status berisi salah satu dari perintah berikut:
- blank = tidak melakukan apa-apa (pindah saja ke status berikutnya)
- 1 = tulis satu ke kaset pada posisi kepala saat ini
- 0 = tulis nol pada pita pada posisi kepala saat ini
- panah ke kiri = gerakkan kepala satu langkah ke kiri
- panah ke kanan = gerakkan kepala satu langkah ke kanan
- kondisi: jika nilai di bawah kepala sama dengan nilai yang ditunjukkan dalam kuadrat turun ke baris kedua negara. jika tidak, pindah ke status berikutnya ke kanan
- lompat kiri: kembali ke keadaan sebelumnya (tetap) tetapi hanya di baris atas [saya awalnya lupa itu, terima kasih @Marzio!]
Tidak ada cara untuk "tumpang tindih" dua lompatan (satu di atas yang lain). Mesin berhenti ketika ada yang meninggalkan status dan tidak ada status berikutnya di sebelah kanannya.
(Setelah mesin berhenti, isi kaset itu dibandingkan dengan isi layar, tetapi saya tidak menganggapnya sebagai bagian dari fungsi mesin yang dimaksud.)
Jawaban:
Berasumsi bahwa:
Saya mencoba membangun konfigurasi mesin Doodle Alan Turing yang mengemulasi mesin dijelaskan dalam " Mesin Turing Kecil dan kompetisi berang-berang yang digeneralisasi secara umum " yang memiliki masalah penghentian yang tergantung pada masalah Collatz yang terbuka (setahu saya). Gambar lengkap tersedia di sini .M.4
... jadi bahkan jika Doodle AT mungkin bukan Turing lengkap (karena operator lompat-satunya yang tidak tumpang tindih yang hanya tersedia di baris pertama), itu cukup kuat untuk berjalan di garis halus (tidak) kepastian: - D
Suntingan: MENGAMBIL DOODLE ADALAH SELAMAT SELESAI
(Saya meninggalkan jawaban sebelumnya di atas, karena saya tidak yakin bagian ini benar :-)
Saya pikir bahkan dengan satu lompatan kiri yang tidak tumpang tindih, Turing Doodle sudah selesai! . Gagasan (sederhana) adalah menggunakan rekaman itu sendiri untuk menyimpan keadaan saat ini dan menggunakan banyak sel untuk mewakili alfabet yang lebih besar.
Sebagai contoh 2 status 8 simbol TM dapat disimulasikan menggunakan representasi rekaman berikut:
Doodle Turing dapat:
Gambar lengkap tersedia di sini .
Dengan cara yang sama, diberikan dengan jumlah negara dan simbol alfabet yang sewenang-wenang kita dapat membangun mesin Turing yang setara .TM. D M
sumber
alen turing
. Saya senang membaca iniIni adalah kutipan dari kertas Turing asli "On Computable Numbers, dengan Aplikasi ke Entscheidungsproblem".
Seorang teman baik modern untuk kertas yang saya rekomendasikan adalah The Annotated Turing oleh Charles Petzold.
Seperti yang Anda lihat, Google hanya berusaha menyerupai mesin yang sangat mirip dengan deskripsi Turing.
EDIT: Mengasumsikan alfabet lengkap Google TM adalah yang ditunjukkan pada akhir permainan setelah mengklik ikon kelinci , dan mengambil dari fakta bahwa itu menghasilkan urutan yang tak terbatas , mendapat lebih banyak baris dan kolom (sehingga kita dapat mengasumsikan kita dapat menambahkan ), telah meninggalkan lompatan (dan juga tumpang tindih kiri) pada setiap baris , memiliki lompatan bersyarat dan tanpa syarat antara baris yang berdekatan, saya pikir itu Turing lengkap .
sumber
Dalam teka-teki, lompatan diperbolehkan di kedua garis, tetapi mereka tidak bisa tumpang tindih. Pada orat-oret kelinci-urutan terakhir pada akhir permainan, mereka memungkinkan melompat pada setiap baris dan mereka bisa bersarang braket sehingga dan [()] diizinkan, tetapi ([)] tampaknya tidak diizinkan.
Saya akan menggunakan asumsi berikut:
Dengan asumsi ini, Mesin Google Doodle Turing Lengkap .
GDM mensimulasikan TM sebagai berikut:
Pilih TM universal favorit Anda dan terapkan dalam prosedur di atas untuk mendapatkan GDM universal.
sumber