Mengapa Mesin Turing model komputasi yang populer?

Saya seorang sarjana CS. Saya mengerti bagaimana Turing menghasilkan mesin abstraknya (memodelkan seseorang yang melakukan perhitungan), tetapi bagi saya tampaknya adalah abstraksi yang canggung dan tidak masuk akal. Mengapa kita mempertimbangkan "pita", dan kepala mesin menulis simbol, mengubah keadaan, menggeser pita itu maju dan mundur?

Apa signifikansi yang mendasarinya? DFA elegan - sepertinya menangkap dengan tepat apa yang diperlukan untuk mengenali bahasa reguler. Tetapi mesin Turing, menurut penilaian pemula saya, hanyalah alat abstrak yang kikuk.

Setelah memikirkannya, saya pikir model perhitungan yang paling ideal adalah dengan mengatakan bahwa beberapa sistem fisik yang sesuai dengan string input, setelah digerakkan, akan mencapai keseimbangan statis yang, pada interpretasi yang setara dengan yang digunakan untuk membentuk sistem dari string asli, akan sesuai dengan string output yang benar. Ini menangkap gagasan "otomatisasi", karena sistem akan berubah secara deterministik hanya berdasarkan keadaan asli.

Edit :

Setelah membaca beberapa tanggapan, saya menyadari bahwa yang membingungkan saya tentang mesin Turing adalah sepertinya tidak minimal. Tidakkah seharusnya model perhitungan kanonik dengan jelas menyampaikan esensi dari komputasi?

Juga, kalau-kalau tidak jelas saya tahu bahwa DFA bukan model lengkap dari perhitungan.

Terima kasih atas balasannya.

Yah, DFA hanyalah mesin Turing yang hanya diperbolehkan untuk bergerak ke kanan dan yang harus menerima atau menolak segera setelah kehabisan karakter input. Jadi saya tidak yakin orang bisa benar-benar mengatakan bahwa DFA itu alami tetapi mesin Turing tidak.

Kritik dari pertanyaan samping, ingat bahwa Turing berfungsi sebelum komputer ada. Karena itu, dia tidak mencoba untuk mengkodifikasikan apa yang dilakukan komputer elektronik, tetapi lebih tepatnya, perhitungan secara umum. Orang tua saya memiliki kamus dari tahun 1930-an yang mendefinisikan komputer sebagai "seseorang yang menghitung" dan ini pada dasarnya dari mana Turing berasal: baginya, pada saat itu, perhitungannya adalah tentang aturan slide, tabel log, pensil dan selembar kertas. Dalam pola pikir itu, menulis ulang simbol pada pita kertas tidak tampak seperti abstraksi yang buruk.

OKE, baiklah, Anda mengatakan (saya harap!) Tetapi kita tidak berada di tahun 1930-an lagi jadi mengapa kita masih menggunakan ini? Di sini, saya tidak berpikir ada satu alasan khusus. Keuntungan dari mesin Turing adalah bahwa mereka cukup sederhana dan kami cukup baik dalam membuktikan hal-hal tentang mereka. Meskipun secara formal menentukan program mesin Turing untuk melakukan beberapa tugas tertentu sangat membosankan, setelah Anda melakukannya beberapa kali, Anda memiliki intuisi yang masuk akal tentang apa yang dapat mereka lakukan dan Anda tidak perlu lagi menulis spesifikasi formal. Model ini juga mudah diperluas untuk memasukkan fitur alami lainnya, seperti akses acak ke kaset. Jadi mereka adalah model yang sangat berguna yang kami pahami dengan baik dan kami juga memiliki pemahaman yang cukup baik tentang bagaimana mereka berhubungan dengan komputer yang sebenarnya.

Seseorang dapat menggunakan model lain tetapi kemudian harus melakukan sejumlah besar terjemahan antara hasil untuk model baru dan tubuh besar dari pekerjaan yang ada pada apa yang dapat dilakukan mesin Turing. Tidak ada yang datang dengan penggantian untuk mesin Turing yang memiliki keuntungan cukup besar untuk membuatnya terlihat seperti ide yang bagus.

Anda mengajukan beberapa pertanyaan berbeda. Izinkan saya menjawabnya secara singkat satu per satu.

Apa yang begitu penting tentang model mesin Turing?

$\lambda$

Pada saat itu, upaya Turing dalam menentukan komputabilitas tampak sebagai yang paling memuaskan. Akhirnya ternyata semua model komputasi yang dijelaskan di atas adalah setara - mereka semua menggambarkan gagasan komputabilitas yang sama. Untuk alasan historis, model Turing keluar sebagai cara paling kanonik untuk mendefinisikan komputasi. Model ini juga sangat sederhana dan sangat mudah untuk dikerjakan, dibandingkan dengan banyak model lain termasuk yang tercantum di atas.

Ilmu komputer yang biasa mengajarkan mesin Turing sebagai definisi komputabilitas, dan kemudian menggunakannya juga untuk mengeksplorasi teori kompleksitas. Tetapi algoritma dianalisis sehubungan dengan model yang lebih realistis yang dikenal sebagai mesin RAM, meskipun masalah ini biasanya disembunyikan sebagai rahasia untuk cognoscenti.

Bukankah DFA model yang lebih baik?

Ini adalah motivasi asli di balik makalah terkenal Rabin dan Scott, Finite automata dan masalah keputusan mereka:

Mesin Turing secara luas dianggap sebagai prototipe abstrak dari komputer digital; Namun, para pekerja di lapangan semakin merasa bahwa gagasan tentang mesin Turing terlalu umum untuk dijadikan model akurat komputer yang sebenarnya. Telah diketahui dengan baik bahwa bahkan untuk perhitungan sederhana tidak mungkin untuk memberikan apriori batas atas pada jumlah pita yang dibutuhkan mesin Turing untuk setiap perhitungan yang diberikan. Justru fitur ini yang membuat konsep Turing tidak realistis.

Dalam beberapa tahun terakhir gagasan otomat terbatas telah muncul dalam literatur. Ini adalah mesin yang hanya memiliki sejumlah kondisi internal terbatas yang dapat digunakan untuk memori dan komputasi. Pembatasan keterbatasan tampaknya memberikan perkiraan yang lebih baik terhadap gagasan mesin fisik. Tentu saja, mesin seperti itu tidak dapat melakukan sebanyak mesin Turing, tetapi keuntungan dari dapat menghitung fungsi rekursif umum sewenang-wenang dipertanyakan, karena sangat sedikit dari fungsi-fungsi ini muncul dalam aplikasi praktis.

Ternyata, meskipun mesin Turing terlalu kuat, DFA terlalu lemah . Saat ini para ahli teori lebih menyukai gagasan perhitungan waktu polinomial , meskipun gagasan ini juga bukan tanpa masalah. Yang mengatakan, DFA dan NFA masih memiliki kegunaannya, terutama dalam kompiler (digunakan untuk analisis leksikal) dan perangkat jaringan (digunakan untuk penyaringan yang sangat efisien).

Bukankah model mesin Turing terlalu terbatas?

The Gereja-Turing tesis menyatakan bahwa mesin Turing menangkap gagasan fisik komputabilitas. Yuri Gurevich telah memimpin upaya untuk membuktikan tesis ini, dengan merumuskan kelas yang lebih umum dari perangkat perhitungan yang dikenal sebagai mesin keadaan abstrak dan membuktikan bahwa mereka setara dalam kekuatan untuk mesin Turing. Mungkin mesin-mesin ini analog dengan model ideal Anda.

Signifikansi yang mendasarinya adalah tentang gagasan Turing-kesetaraan. Model yang tepat tidak penting, asalkan setara dengan Turing. Tetapi lebih baik menggunakan model yang lebih sederhana sehingga Anda bisa membuktikan kesetaraan dengan model lain lebih mudah.

Lebih tepatnya, lebih baik untuk membuatnya lebih mudah untuk mensimulasikan model ini di model lain, seperti yang kita tahu sebagian besar bahasa pemrograman maju setara dengan Turing (dengan asumsi tertentu tentang alamat memori) dan dapat digunakan untuk mensimulasikan model lain.

Ada model lain, seperti kalkulus lambda dan tata bahasa (string penulisan ulang). Tetapi lebih mudah untuk mendefinisikan batasan waktu dan ruang dalam mesin Turing. Anda juga dapat menggunakan bahasa pemrograman seperti Brainfuck, tetapi membutuhkan kerja yang tidak perlu misalnya mendefinisikan ulang simbol untuk mendapatkan modifikasi yang secara logis sepele.

Jadi, mesin Turing sepertinya cukup cocok untuk saya jika Anda harus belajar satu model untuk semuanya. Tetapi jika Anda akan mempelajari banyak model, saya tidak melihat ada salahnya untuk mempelajari kalkulus lambda untuk ide Turing-equivalence, Brainfuck untuk membuktikan model lain Turing-ekivalen, dan bahasa pemrograman praktis (lebih baik dengan stack yang dapat diakses dan tidak ada variabel tersembunyi) untuk kendala waktu / ruang, dan hanya menganggap mesin Turing alat untuk membuktikan hal-hal ini setara jika tidak ada yang repot menemukan cara mengatasinya. Ini secara alami terjadi jika Anda tidak memulai dengan mempelajari teori yang mendasarinya terlebih dahulu, tetapi hanya melakukannya ketika Anda menemukannya berguna.

Saya ingin menanggapi bagian dari pertanyaan ini, ditambahkan dalam edit:

"Bukankah seharusnya model perhitungan kanonik jelas menyampaikan esensi dari komputabilitas?"

$T$$T$$T$

Itulah salah satu esensi dari komputasi: Apa pun gagasan umum tentang komputasi yang ada dalam pikiran seseorang, harus ada satu mesin yang melakukan semuanya. Itulah yang dilakukan mesin Turing universal. Itu juga yang dilakukan komputer modern (tunduk pada idealisasi yang secara fisik tidak realistis memiliki memori tanpa batas).

Cara lain untuk menempatkan ini, yang secara langsung menjawab kekhawatiran Anda bahwa mesin Turing tidak minimal, adalah bahwa mesin itu hanya seminimal mungkin, tergantung pada persyaratan bahwa mereka menggambarkan gagasan umum tentang komputabilitas yang terdapat mesin universal.

Mesin Turing tidak dimaksudkan untuk digunakan secara harfiah; pemrograman di dalamnya adalah sesuatu yang hanya akan dilakukan sekali sebagai latihan, untuk memahami bagaimana mereka bekerja.

Mereka secara khusus tidak dibuat untuk "melakukan" apa pun. Mereka tidak perlu minimal, mereka tidak perlu nyaman untuk bekerja dengannya.

Mereka hanyalah model mesin yang bisa Anda buat, yang akan sama ekspresif dan kuatnya dengan mesin lain yang pernah Anda buat di dunia fisik (sejauh yang kita kenal sekarang).

Mereka didefinisikan oleh Turing sebagaimana adanya karena alasan-alasan utama ini:

• Untuk dapat membuktikan bahwa mereka mencakup semua dan semua algoritma yang dapat kita pikirkan.
• Untuk mengerjakan masalah penghentian / masalah keputusan.
• Untuk dapat mengurangi mesin / bahasa lain ke yang ini.

Apakah mungkin untuk memilih bahasa lain? Tentunya! Bahasa lengkap apa pun yang kita kenal sekarang bisa digunakan. Tetapi akan jauh lebih sulit untuk membangun landasan teori pada mesin yang lebih kompleks.

Saya berpendapat bahwa mereka bahkan bukan "model perhitungan yang populer"; tak seorang pun akan menghitung apa pun dengan Mesin Turing. Ini adalah konsep teoritis murni, yang dibuat oleh para ilmuwan komputer teoretis, untuk tcs's.

Mengapa ini populer, mungkin yang paling populer? Anda harus ingat bahwa Turing menciptakan "mesin" ini bertahun-tahun sebelum komputer elektronik. TM dioperasikan dengan kertas, pena, karet, dan yang terakhir, otak manusia. Jadi semua orang dapat menjalankan "perhitungan" dengan mesin ini. Semua orang berarti seseorang yang tidak pernah belajar komputer, pemrograman bahasa. Mudah digunakan. Ketika Anda memikirkannya, Anda menemukan sebuah paradoks: mesin ini adalah kumpulan hampir tidak ada tetapi Anda dapat mengoperasikan semuanya. Menurut pendapat saya paradoks "hampir-tidak ada / versus / segalanya" adalah alasan mengapa itu populer. Saya akan memperhatikan bahwa TM tidak secara eksplisit menjelaskan rekursi, TM hanya berurusan dengan "lompatan". Fitur itu (secara eksplisit berbicara tentang rekursi) dapat menjadi sumber headhache untuk pemula, misalnya dalam lambda-calculus konsep Y-combinator hampir tidak dapat dimengerti; Lebih tepatnya, TM populer karena paradoks "hampir-tidak ada / versus / semuanya" tanpa headhache rekursi.