Apakah ada analogi fisik dengan Mesin Turing?

Baru-baru ini di kelas CS saya, saya diperkenalkan dengan Mesin Turing.

Setelah kelas, saya menghabiskan lebih dari 2 jam mencoba mencari tahu apa hubungan antara kaset dan mesin.

Saya sama sekali tidak menyadari keberadaan kaset komputer atau bagaimana kaset dan mesin berinteraksi sampai hari ini. Saya masih tidak dapat melihat mengapa sebuah mesin membaca kaset tetapi pemindai mungkin merupakan konsepsi yang lebih dekat dengan mesin Turing di mana kertas dianggap sebagai pita dan apa pun yang masuk ke dalam pemindai adalah apa pun yang dilakukan mesin Turing.

Tapi bagaimanapun juga, bukankah ide mesin Turing itu cukup kuno? Kami memiliki begitu banyak perangkat fisik (bukan hipotetis) di kantor atau ruang tamu kami yang tampaknya melakukan apa yang dilakukan Mesin Turing.

Dapatkah seseorang memberikan contoh yang lebih baik dari realitas sehingga fungsi esensial dari konsepsi hipotetis ini ditangkap?

Mesin Turing adalah salah satu model komputasi Turing-lengkap "asli", bersama dengan kalkulus dan fungsi rekursif yang didefinisikan secara rekursif. Saat ini di banyak bidang ilmu komputer teoretis model yang berbeda digunakan, mesin RAM, yang jauh lebih dekat dengan komputer yang sebenarnya. Karena kedua model adalah p-ekuivalen (mereka mensimulasikan satu sama lain dengan paling banyak polinomial blow-up), dari sudut pandang pertanyaan seperti P vs NP, kedua model itu setara.$\lambda$

AFAIK Mesin Turing dimodelkan pada gagasan manusia dengan pena dan kertas. Manusia memiliki keadaan tertentu di otak, melihat kertas seperti mesin melihat rekaman, dan menulis sesuatu di kertas atau bergerak untuk melihat tempat yang berbeda, seperti halnya mesin.

TM kuno sebagai aritmatika bilangan alami Peano. TM tidak berguna untuk perhitungan praktis, dan tentu saja tidak dimaksudkan untuk digunakan untuk itu. Ini hanya cara sederhana untuk aksiomatiskan perhitungan sehingga kita dapat berpikir tentang apa yang dapat dihitung dan apa yang tidak - seperti aritmatika Peano berguna untuk menentukan dari prinsip pertama apa bilangan alami, dan apa sifat-sifatnya - tetapi akan konyol untuk coba lakukan aritmatika dengan memanipulasi angka Peano dengan tangan sesuai dengan definisi teoretis.

Bayangkan betapa sulitnya membuktikan teorema yang berbeda dari teori kompleksitas dan komputabilitas (mis. Buktikan bahwa Masalah Pemutusan tidak dapat diputuskan), jika Anda harus membuktikannya menggunakan semantik bahasa pemrograman C ++ alih-alih Mesin Turing. Bukti Anda akan menjadi konyol atau tidak mungkin - sama konyolnya dengan membuktikan asosiasi dari perkalian bilangan alami dengan menggunakan metode sekolah dasar yang diterapkan pada bilangan desimal sebagai definisi Anda tentang apa perkalian itu.

Banyak model perhitungan lengkap Turing yang sangat berbeda dapat direalisasikan secara fisik (hingga mempertimbangkan tak terhingga sebagai kepanjangan dari ketidakterbatasan). Jadi itu tidak bisa menjadi titik untuk memilih model.

Jawaban oleh @jkff tepat dalam menyatakan bahwa Mesin Turing dimaksudkan sebagai perangkat teoretis untuk tujuan matematis mempelajari kemampuan komputasi dan provabilitas (muncul sebenarnya dalam konteks Hilbert's Entscheidungsproblem ). Tetapi itu tidak cukup akurat dalam alasan memilih formalisme sederhana.

Membuktikan pada prinsipnya masalah Berhenti tidak jauh lebih sulit dengan model yang lebih maju. Faktanya, "bukti" kita seringkali hanya merupakan konstruksi dari solusi. Kami tidak banyak membahas argumen yang sebenarnya (sangat membosankan) bahwa konstruksi ini benar. Tetapi siapa pun yang menulis penerjemah untuk bahasa lengkap Turing melakukan sebanyak konstruksi mesin universal. Yah, C bisa sedikit rumit, dan kami mungkin ingin merampingkannya sedikit untuk tujuan seperti itu.

Pentingnya memiliki model sederhana berada jauh lebih banyak dalam penggunaan yang dapat dibuat dari model, daripada dalam membangun sifat-sifatnya (seperti Masalah terputus-putus, untuk mengambil contoh yang diberikan oleh @jkff).

Biasanya, teorema agung sering merupakan teorema yang dapat diekspresikan dengan sangat sederhana dan dapat diterapkan pada berbagai masalah. Tetapi mereka belum tentu merupakan teorema yang mudah dibuktikan.

Dalam kasus TM, pentingnya kesederhanaan adalah karena banyak hasil ditetapkan dengan mengurangi Masalah Pemutusan, atau masalah TM lainnya, untuk masalah yang kami minati (seperti ambiguty dari bahasa bebas-konteks), sehingga menetapkan batasan yang melekat pada penyelesaian masalah-masalah ini.

Bahkan, meskipun sangat intuitif (yang mungkin merupakan alasan utama popularitasnya), model TM seringkali tidak cukup sederhana untuk digunakan dalam pembuktian tersebut. Itulah salah satu alasan pentingnya beberapa model lain yang lebih sederhana, seperti Post Correspondence Problem , kurang intuitif untuk dianalisis, tetapi lebih mudah digunakan. Tapi ini karena model komputasi ini sering digunakan untuk membuktikan hasil negatif (yang kembali ke Entscheidungsproblem asli).

Namun, ketika kami ingin membuktikan hasil positif, seperti keberadaan algoritma untuk memecahkan beberapa masalah yang diberikan, TM adalah perangkat yang terlalu sederhana. Jauh lebih mudah untuk mempertimbangkan mode model lanjutan seperti komputer RAM , atau komputer memori asosiatif , atau salah satu dari banyak model lain, atau bahkan hanya salah satu dari banyak bahasa pemrograman.

Kemudian model TM datang hanya sebagai titik referensi, khususnya untuk analisis kompleksitas, mengingat kompleksitas mengurangi model-model ini ke model TM (biasanya polinomial). Kesederhanaan model TM meminjamkan banyak kredibilitas untuk ukuran kompleksitas (sebagai lawan, untuk mengambil contoh ekstrim, untuk pengurangan Lambda-calculus).

Dengan kata lain, model TM seringkali terlalu sederhana untuk merancang dan mempelajari algoritma (hasil positif), dan seringkali terlalu kompleks untuk mempelajari kemampuan komputasi (hasil negatif).

Tetapi tampaknya berada di tempat yang tepat untuk melayani sebagai tautan sentral untuk menghubungkan semuanya, dengan keuntungan besar karena menjadi agak intuitif.

Mengenai analogi fisik, tidak ada alasan untuk memilih satu model dari yang lain. Banyak model komputasi lengkap Turing dapat direalisasikan secara fisik (hingga tanpa batas untuk memori tak terhingga), karena tidak ada alasan untuk menganggap komputer bersama-sama dengan perangkat lunaknya sebagai kurang fisik daripada komputer "telanjang". Bagaimanapun, perangkat lunak memiliki representasi fisik, yang merupakan bagian dari komputer yang diprogram. Jadi, karena semua model perhitungan setara dari sudut pandang itu, kami mungkin juga memilih satu yang sesuai untuk organisasi pengetahuan.

Bayangkan seorang pendatang baru di bidang geometri bertanya:

Apakah ada analogi fisik dengan segitiga?

Bukankah ide segitiga itu cukup kuno? Kami memiliki begitu banyak bentuk fisik (bukan hipotetis) di kantor atau ruang tamu kami yang tampaknya melakukan apa yang dilakukan segitiga.

Apa yang akan kamu jawab?

Anda mungkin mengatakan bahwa pertanyaan ini mengungkapkan dua kesalahpahaman mendasar tentang segitiga:

1. "Segitiga itu murni hipotetis." Salah! Sementara mereka adalah entitas matematika, cita-cita Platonis, dan hipotetis dalam pengertian itu, segitiga itu nyata : kita sebenarnya dapat membangunnya di dunia nyata. Memang, apa yang kita bangun tidak akan menjadi segitiga yang sempurna, tetapi teori matematika kita tentang hal itu berlaku untuk dunia nyata, hukum yang dapat kita peroleh berlaku untuk bentuk di dunia nyata, teori ini dapat digunakan sebagai dasar untuk mendesain, membangun dan mengukur bentuk di dunia nyata; inilah alasan mengapa teori ini dikembangkan.
2. "Segitiga tidak berguna karena mereka tidak menggambarkan bentuk yang biasanya kita gunakan."Salah! Menjelaskan bentuk sebenarnya yang Anda temukan di dunia nyata bukanlah tujuan mereka. Jika seluruh kantor atau ruang keluarga Anda tidak mengandung segitiga tunggal, itu tidak berarti konsep segitiga itu tidak realistis atau ketinggalan zaman dan sebaiknya diganti dengan yang lain. Tujuan utama mereka adalah sebagai konstruksi dasar dari mana semua bentuk yang lebih kompleks dapat dibangun pada prinsipnya - dan karenanya kita dapat memperoleh hukum yang berlaku untuk bentuk secara umum. Penalaran tentang segitiga memungkinkan kita untuk alasan tentang bentuk secara umum. Ruang tamu Anda tunduk pada hukum yang sama yang kami peroleh untuk segitiga, dan pengetahuan kami tentang hukum ini digunakan, secara langsung atau tidak langsung, untuk membangunnya. Ruang tamu mungkin tidak memiliki segitiga tunggal di dalamnya, apalagi yang sempurna, tapi kami tidak peduli menemukan segitiga di sana; kita dapat. namun, buat deskripsi bentuk di sana dengan memperkirakannya dengan segitiga, dan ini - triangulasi - adalah hal yang populer dan berguna untuk dilakukan. Jadi segitiga adalah blok bangunan untuk membantu kita berpikir tentang bentuk secara umum.

Hal yang sama berlaku untuk mesin Turing.

Sudah begitu lama sejak saya diperkenalkan ke geometri, saya benar-benar tidak bisa mengingat apakah ada pendatang baru yang benar-benar memiliki kesalahpahaman tentang segitiga. Tetapi ketika datang ke mesin Turing, saya menemukan kesalahpahaman ini sepanjang waktu . Begitu sering, pada kenyataannya, tampaknya ada sesuatu yang secara fundamental salah dengan cara mereka biasanya diajarkan. Mungkin pendekatan show and tell sudah beres!

Jadi, demi kelengkapan:

1. "Mesin Turing murni hipotetis." Salah! Sementara mereka adalah entitas matematika, cita-cita Platonis, dan hipotetis dalam pengertian itu, Mesin Turing adalah nyata : kita sebenarnya dapat membangunnya di dunia nyata. Memang, apa yang kita bangun tidak akan pernah menjadi Mesin Turing yang sempurna, tetapi teori matematika kita tentang mereka tidak berlaku untuk dunia nyata, hukum yang dapat kita peroleh berlaku untuk perangkat komputasi di dunia nyata, teori ini dapat digunakan sebagai dasar untuk merancang, membangun, dan mengukur perangkat komputasi di dunia nyata; inilah alasan mengapa teori ini dikembangkan.
2. "Mesin Turing tidak berguna karena mereka tidak menggambarkan perangkat komputasi yang biasanya kita gunakan."Salah! Menjelaskan perangkat komputasi yang sebenarnya Anda temukan di dunia nyata bukanlah tujuan mereka. Jika seluruh kantor belakang atau studio hiburan rumah Anda tidak mengandung Mesin Turing tunggal, itu tidak berarti konsep Mesin Turing tidak realistis atau ketinggalan zaman dan sebaiknya diganti dengan yang lain. Tujuan utamanya adalah sebagai konstruksi dasar dari mana semua perangkat komputasi yang lebih kompleks dapat dibangun secara prinsip - dan karenanya kita dapat memperoleh hukum yang berlaku untuk bentuk secara umum. Penalaran tentang Mesin Turing memungkinkan kita untuk alasan tentang perangkat perhitungan secara umum. Perangkat keras dan perangkat lunak komputer Anda tunduk pada undang-undang yang sama yang telah kami peroleh untuk Mesin Turing, dan pengetahuan kami tentang undang-undang ini digunakan, secara langsung atau tidak langsung, untuk membuatnya - meskipun mungkin tidak t memiliki Mesin Turing tunggal di dalamnya. Itu hukum yang kami minati.

Analogi fisik yang tampaknya dimiliki Turing dalam benaknya adalah komputer yang mengerjakan masalah dengan pensil, kertas, dan penghapus. Anda harus memahami bahwa pada tahun 1936, "komputer" adalah orang yang digunakan untuk menghitung. Tentu saja pada tahun 1936 sebagian besar komputer akan menggunakan mesin tambah, tetapi Turing tidak menyebutkan ini karena mereka tidak penting. Inilah yang dia katakan, sehubungan dengan rekaman itu, dalam mencoba membenarkan bahwa "angka-angka 'yang dapat dihitung' [yaitu yang dapat dihitung oleh mesin Turing] termasuk semua angka yang secara alami akan dianggap sebagai yang dapat dihitung"

Komputasi biasanya dilakukan dengan menulis simbol-simbol tertentu di atas kertas. Kita mungkin mengira makalah ini dibagi menjadi kotak-kotak seperti buku aritmatika anak-anak. Dalam aritmatika dasar, karakter dua dimensi dari kertas kadang-kadang digunakan. Tetapi penggunaan seperti itu selalu dapat dihindari, dan saya pikir akan disetujui bahwa karakter dua dimensi kertas tidak penting dalam perhitungan. Saya berasumsi kemudian bahwa perhitungan dilakukan pada kertas satu dimensi, yaitu pada pita yang dibagi menjadi kotak.

Meskipun komputer tidak lagi merupakan perdagangan, terakhir kali saya memeriksa, anak-anak masih diajarkan untuk mengeksekusi algoritma menggunakan pensil dan kertas sebagai media penyimpanan. Jadi, meskipun analogi ini mungkin tampak kuno atau bahkan kuno, itu belum usang.

Untuk selengkapnya, lihat Pada nomor yang dapat dihitung dengan aplikasi ke entscheidungsproblem , terutama bagian 1 dan 9.

@ jkff memiliki gagasan tentang the Turing Machine is modeled on the idea of a human with a pen and papertidak sepenuhnya benar. Tetapi ada banyak situasi di mana itu dapat dianggap benar.

Pikirkan manusia sebagai mesin Turing di bawah proyeksi negara bagian tertentu. Dengan kata lain, jika Anda melihat manusia hanya selama jam kerjanya, maka selama jam kerjanya ia melakukan tugas-tugas tertentu. Tugas-tugas ini adalah tugas dasar untuk pekerjaan itu.

Jika Anda tidak peduli dengan kehidupan pribadinya, apa yang dia lakukan di rumah, di kamarnya, dll. Maka Anda dapat menganggap ini sebagai memproyeksikan fungsi transisinya menjadi fungsi transisi baru di mana negara-negara yang tidak terkait dengan pekerjaan diabaikan. Dengan kata lain, Anda dapat melewati semua status dan tugas yang tidak ada hubungannya dengan kepedulian dan perspektif Anda.

Dalam model ini, maka mesin Turing dimodelkan setelah manusia dengan pena, kertas melakukan tugas tetap (yaitu melihat dalam perspektif tetap). Rekaman itu adalah apa yang dia tulis di atas kertas (mengabaikan semua kertas atau menulis di atas kertas yang dia tidak tulis untuk tugas itu)

Sekarang jika Anda mempertimbangkan tugas-tugas lain yang dia lakukan maka apa yang Anda miliki adalah Anda memiliki penyatuan banyak mesin Turing pada manusia. Tetapi kemudian bagaimana jika dia mengubah pekerjaannya dan dia melakukan tugas yang berbeda. Kemudian keadaan otaknya berubah menjadi mesin Turing yang berbeda ketika dilihat dalam perspektif yang berbeda dalam kerangka waktu yang berbeda.

Jika Anda ingin jawaban yang baik untuk pertanyaan Anda, maka saya pikir Yuval Filmus menjawabnya dengan baik. Gunakan model RAM. Tetap dengan itu.