Alasan historis untuk adopsi Mesin Turing sebagai model utama perhitungan.

Ini pemahaman saya bahwa model Turing telah menjadi "standar" ketika menjelaskan perhitungan. Saya tertarik untuk mengetahui mengapa hal ini terjadi - yaitu, mengapa model TM menjadi lebih banyak digunakan daripada model lain yang setara secara teori (sepengetahuan saya), misalnya urs-Rekursi Kleene atau Kalkulus Lambda (saya mengerti bahwa yang pertama tidak muncul sampai nanti dan yang terakhir tidak pada awalnya dirancang khusus sebagai model perhitungan, tetapi itu menunjukkan bahwa alternatif telah ada sejak awal).

Yang bisa saya pikirkan adalah bahwa model TM lebih dekat mewakili komputer yang sebenarnya kita miliki daripada alternatifnya. Apakah ini satu-satunya alasan?

Ini tampaknya benar dalam konteks (beberapa bidang) ilmu komputer tetapi tidak secara umum.

Salah satu alasan berkaitan dengan Tesis Gereja. Alasan utama adalah bahwa beberapa ahli seperti Godel tidak berpikir bahwa argumen bahwa model komputasi sebelumnya / lainnya menangkap konsep komputasi intuitif yang meyakinkan. Ada berbagai argumen, Gereja punya beberapa, tetapi mereka tidak meyakinkan Godel. Di sisi lain analisis Turing itu meyakinkan untuk Godel sehingga diterima sebagai yang model untuk perhitungan yang efektif. Kesetaraan antara model yang berbeda terbukti kemudian (saya pikir oleh Kleene).

Alasan kedua adalah teknis dan perkembangan selanjutnya terkait dengan studi teori kompleksitas. Menentukan ukuran kompleksitas seperti waktu, ruang, dan nondeterminisme tampaknya lebih mudah menggunakan mesin Turing daripada model lain seperti fungsi -calculus dan -recursive.$\lambda$$\mu$

Di sisi lain, fungsi rekursif dulu dan masih digunakan sebagai cara utama untuk mendefinisikan komputabilitas dalam buku teori logika dan komputabilitas. Mereka lebih mudah untuk dikerjakan ketika seseorang hanya peduli tentang efektivitas dan bukan tentang kompleksitas. Buku Kleene "Metamathematics" sangat berpengaruh untuk perkembangan ini. Juga -calculus tampaknya lebih umum di CMU / ilmu komputer gaya Eropa seperti bahasa pemrograman dan tipe teori. Beberapa penulis lebih suka model RAM dan Mesin Register. (Sepertinya saya bahwa karena alasan tertentu orang Amerika mengadopsi model semantik Turing dan Eropa mengadopsi model sintaksis Gereja, Chruch adalah orang Amerika dan Turing adalah orang Inggris. Ini pendapat / pengamatan pribadi dan yang lain memiliki pandangan berbeda$\mu$$\lambda$. Lihat juga makalah ini oleh Viggo Stoltenberg-Hansen dan John V. Tucker I , II .)

Beberapa sumber untuk bacaan lebih lanjut:

Robert I. Soare memiliki sejumlah artikel tentang sejarah perkembangan ini, saya pribadi suka yang ada di Buku Pegangan Teori Komputasi. Anda dapat menemukan lebih banyak dengan memeriksa referensi di makalah itu.

Sumber lain yang bagus adalah artikel komputabilitas Neil Immerman tentang SEP, lihat juga artikel Tesis Gereja-Turing oleh B. Jack Copeland.

Karya -karya yang dikumpulkan Godel berisi banyak informasi tentang pandangannya. Pengantar khusus untuk artikelnya ditulis dengan sangat baik.

" Metamathematics " karya Kleene adalah buku yang sangat bagus.

Terakhir, jika Anda masih belum puas, periksa arsip milis FOM , dan jika Anda tidak dapat menemukan jawaban di arsip, poskan email ke milis.

Saya ingin melemahkan klaim bahwa TM adalah model utama perhitungan, atau setidaknya mengarah ke dimensi lain dari pertanyaan. Jelas bahwa TM dominan dalam bagian ilmu komputer yang lebih kompleks dan berorientasi algoritme, tetapi dalam teori dan praktik bahasa pemrograman, mereka tidak terlalu dominan. Ada berbagai alasan untuk ini, tetapi mungkin yang paling penting adalah bahwa TMs atau program yang berjalan pada TMs (tidak seperti misalnya lambda-calculi atau proses-calculi) tidak dibangun dengan cara aljabar. Ini membuatnya sulit untuk mengembangkan teori tipe, yang telah menjadi andalan teori bahasa pemrograman.

Salah satu hal yang menyenangkan tentang mesin Turing adalah mereka bekerja pada string, bukan bilangan alami atau istilah lambda, karena input dan output dari banyak masalah dapat dirumuskan secara alami sebagai string. Saya tidak tahu apakah ini dianggap sebagai alasan "historis" atau tidak.

Selain fakta bahwa mesin Turing adalah model komputasi pena-dan-kertas yang meyakinkan (“gagasan intuitif tentang komputasi”), saya pikir mereka memiliki serangkaian fitur yang sering berguna, terutama ketika membuktikan teorema tentang mereka:

• mereka mudah dijelaskan secara formal dan memiliki semantik operasional yang sederhana;
• mudah untuk memberikan definisi konkret tentang kompleksitas waktu dan ruang mereka;
• model komputer elektronik yang lebih realistis (dan kompleks), seperti mesin akses acak, dapat disimulasikan oleh TM dengan overhead polinomial, dan sebaliknya.

Itu adalah yang pertama memiliki dampak dan dengan demikian telah ditetapkan, terutama dalam teori kompleksitas. Ini adalah alasan yang lemah, tetapi orang bekerja seperti itu. Kami mengerjakan masalah lama yang terbuka terlebih dahulu alih-alih mendeklarasikan yang baru.