Komputer nyata hanya memiliki jumlah negara terbatas, jadi apa relevansi mesin Turing dengan komputer nyata?

Komputer nyata memiliki memori yang terbatas dan hanya sejumlah negara terbatas. Jadi mereka pada dasarnya automata terbatas. Mengapa ilmuwan komputer teoretis menggunakan mesin Turing (dan model lain yang setara) untuk mempelajari komputer? Apa gunanya mempelajari model yang jauh lebih kuat ini sehubungan dengan komputer nyata? Mengapa model automata terbatas tidak cukup?

Ada dua pendekatan ketika mempertimbangkan pertanyaan ini: historis yang berkaitan dengan bagaimana konsep ditemukan dan teknis yang menjelaskan mengapa konsep tertentu diadopsi dan yang lainnya ditinggalkan atau bahkan dilupakan.

Secara historis, Mesin Turing mungkin merupakan model paling intuitif dari beberapa yang dikembangkan yang mencoba menjawab Entscheidungsproblem . Ini terkait erat dengan upaya besar dalam dekade pertama abad ke-20 untuk sepenuhnya aksioma matematika. Harapannya adalah bahwa sekali Anda telah membuktikan set aksioma kecil menjadi benar (yang akan membutuhkan upaya substansial), Anda kemudian dapat menggunakan metode sistematis untuk memperoleh bukti untuk pernyataan logis yang Anda minati. Bahkan jika seseorang dianggap automata terbatas dalam konteks ini, mereka akan segera diberhentikan karena mereka gagal menghitung bahkan fungsi sederhana.

Secara teknis, pernyataan bahwa semua komputer adalah automata terbatas adalah salah. Otomat terbatas memiliki memori konstan yang tidak dapat diubah tergantung pada ukuran input. Tidak ada batasan, baik dalam matematika maupun kenyataan, yang mencegah menyediakan kaset tambahan, hard disk, RAM atau bentuk memori lainnya, begitu memori dalam mesin digunakan. Saya percaya ini sering digunakan pada hari-hari awal komputasi, ketika bahkan perhitungan sederhana dapat mengisi memori, sedangkan sekarang untuk sebagian besar masalah dan dengan infrastruktur modern yang memungkinkan manajemen memori yang jauh lebih efisien, ini sebagian besar waktu bukan masalah .

EDIT: Saya menganggap kedua poin yang diangkat dalam komentar tetapi memilih untuk tidak memasukkan keduanya singkat dan waktu yang saya miliki untuk menuliskan jawabannya. Ini adalah alasan saya mengapa saya percaya poin-poin ini tidak mengurangi efektivitas mesin Turing dalam mensimulasikan komputer modern, terutama bila dibandingkan dengan automata terbatas:

• Pertama-tama saya akan membahas masalah fisik tentang batas ingatan oleh alam semesta. Pertama-tama, kita tidak benar-benar tahu apakah alam semesta ini terbatas atau tidak. Lebih jauh, konsep alam semesta yang dapat diamati yang secara definisi terbatas, juga menurut definisi tidak relevan bagi pengguna yang dapat melakukan perjalanan ke titik mana pun dari alam semesta yang dapat diamati untuk menggunakan memori. Alasannya adalah bahwa alam semesta yang dapat diamati mengacu pada apa yang dapat kita amati dari titik tertentu, yaitu Bumi, dan akan berbeda jika pengamat dapat melakukan perjalanan ke lokasi yang berbeda di alam semesta. Dengan demikian, setiap argumen tentang alam semesta yang dapat diamati beralih ke pertanyaan tentang keterbatasan alam semesta. Tapi mari kita anggap bahwa melalui beberapa terobosan kita memperoleh pengetahuan bahwa alam semesta memang terbatas. Meskipun ini akan berdampak besar pada masalah ilmiah, Saya ragu itu akan berdampak pada penggunaan komputer. Sederhananya, mungkin pada prinsipnya komputer memang automata terbatas dan bukan mesin Turing. Tetapi untuk mayoritas semata-mata untuk komputasi dan kemungkinan setiap komputasi yang diinginkan manusia, mesin Turing dan teori yang terkait memberi kita pemahaman yang lebih baik. Dalam contoh kasar, meskipun kita tahu bahwa fisika Newton pada dasarnya salah, saya ragu para insinyur mekanik menggunakan terutama fisika kuantum untuk merancang mobil atau mesin pabrik; kasus sudut di mana ini diperlukan dapat ditangani pada tingkat individu. Tetapi untuk mayoritas semata-mata untuk komputasi dan kemungkinan setiap komputasi yang diinginkan manusia, mesin Turing dan teori yang terkait memberi kita pemahaman yang lebih baik. Dalam contoh kasar, meskipun kita tahu bahwa fisika Newton pada dasarnya salah, saya ragu para insinyur mekanik menggunakan terutama fisika kuantum untuk merancang mobil atau mesin pabrik; kasus sudut di mana ini diperlukan dapat ditangani pada tingkat individu. Tetapi untuk mayoritas semata-mata untuk komputasi dan kemungkinan setiap komputasi yang diinginkan manusia, mesin Turing dan teori yang terkait memberi kita pemahaman yang lebih baik. Dalam contoh kasar, meskipun kita tahu bahwa fisika Newton pada dasarnya salah, saya ragu para insinyur mekanik menggunakan terutama fisika kuantum untuk merancang mobil atau mesin pabrik; kasus sudut di mana ini diperlukan dapat ditangani pada tingkat individu.

• $2^{64}$$2^{64}$alamat yang berbeda. Pada dasarnya jaringan adalah cara yang bagus untuk melakukan ini, setiap mesin hanya peduli dengan memori lokal tetapi mereka dapat menghitung bersama.

Untuk menyelesaikan jawaban lain: Saya pikir Turing Machine adalah abstraksi yang lebih baik dari apa yang komputer lakukan daripada automata terbatas. Memang, perbedaan utama antara kedua model adalah bahwa dengan automata terbatas, kami berharap untuk memperlakukan data yang lebih besar dari ruang keadaan, dan Mesin Turing adalah model untuk sebaliknya (keadaan ruang >> data) dengan membuat keadaan ruang tak terbatas. Ketakterhinggaan ini dapat dianggap sebagai abstraksi "sangat besar di depan ukuran data". Saat menulis program komputer, Anda mencoba menghemat ruang untuk efisiensi, tetapi umumnya Anda menganggap bahwa Anda tidak akan dibatasi oleh jumlah total ruang pada komputer. Itu adalah bagian dari alasan mengapa Mesin Turing adalah abstraksi komputer yang lebih baik daripada automata terbatas.

Andrej Bauer memberi satu alasan penting dalam komentar:

$\infty$$10000000000000000000000000000000$$10000000000000000000000000000000$

Biarkan saya melengkapi jawaban lain dengan beberapa poin, yang mungkin terlalu jelas untuk disebutkan:

• Jika tujuan Anda adalah mempelajari komputer sungguhan, maka automata terbatas dan mesin Turing akan sering menjadi model yang terlalu sederhana untuk pertanyaan yang relevan. Komputer nyata memiliki beberapa inti pemrosesan dengan hierarki cache (atau skema manajemen pintar lainnya), akses ke sejumlah memori cepat yang layak, akses ke sejumlah besar memori eksternal yang lambat (hard disk), dan dapat berkomunikasi dengan komputer lain yang sejenis di sebuah kecepatan kira-kira sebanding dengan kecepatan akses ke memori eksternal yang lambat.
• Jika sekarang Anda bertanya pada diri sendiri mengapa Anda membutuhkan semua perincian itu, maka ternyata tujuan Anda yang sebenarnya adalah mempelajari contoh masalah dan seberapa efisien Anda dapat menyelesaikannya. Jika Anda berbicara tentang komputer nyata, ini juga dapat berarti bahwa Anda menjalankan percobaan dengan contoh masalah aktual pada berbagai jenis arsitektur komputer (nyata).
• Model komputer nyata yang dijelaskan di atas masih diidealkan, karena mengabaikan berbagai mode kegagalan komputer nyata. Karena matikan kegagalan mungkin lebih sering daripada kegagalan hard disk (dan hard disk mungkin memiliki cadangan), domain masalah tertentu seperti operasi database yang andal mungkin perlu memperhitungkannya.
• $\Pi_1^0$

Formalisme bermanfaat atau tidak, berdasarkan apa yang orang ingin gunakan formalisme untuk model dan memahami.

Mesin Turing adalah formalisme yang berguna untuk memahami program . Program layak dipahami; sebagian besar perhitungan aktual dilakukan oleh program, bukan oleh mesin tujuan khusus. Formalisme mesin Turing memungkinkan kita untuk memodelkan masalah dunia nyata yang penting seperti kompleksitas waktu dan ruang. Adalah jauh lebih alami untuk mencoba mempelajari gagasan-gagasan ini menggunakan automata negara-terbatas.

Mesin Turing tidak terlalu berguna ketika mencoba mempelajari kompleksitas fungsi komputasi yang terbatas (katakanlah, fungsi yang domainnya terdiri dari input panjang paling banyak 10 juta). Kompleksitas sirkuit jauh lebih baik dalam menggambarkan kompleksitas fungsi hingga ... tetapi mesin Turing pada gilirannya sangat berguna dalam memahami kompleksitas sirkuit.

Automata terbatas juga bermanfaat dalam memahami kompleksitas rangkaian; semua model ini memiliki tempat mereka di gudang matematika.

Saya menolak argumen yang mengatakan automata kondisi-terbatas adalah model realitas yang lebih baik semata-mata karena komputer dunia nyata hanya memiliki sejumlah kondisi internal yang terbatas. Studi tentang keadaan-terbatas automata secara krusial berurusan dengan input yang berasal dari rangkaian string tak terbatas , sedangkan komputer dunia nyata berurusan dengan input dengan hanya beberapa panjang maksimal tetap (kecuali jika Anda percaya bahwa kita hidup di alam semesta tanpa batas, baik dalam hal ruang atau waktu).

Sebuah model harus dinilai dalam hal kegunaannya dalam memahami aspek-aspek realitas yang kita pedulikan. Atau (sebagai alternatif) dalam hal kegunaannya dalam memahami alam semesta matematika yang orang anggap cukup menarik, bahkan jika alam semesta matematika itu tidak memiliki manifestasi fisik yang jelas.

Mesin Turing, mesin negara-terbatas, dan sirkuit (dan model lain di samping) semuanya telah membuktikan kegunaannya.

Komputer yang sebenarnya bukan FSA. Komputer yang sebenarnya adalah komputer universal, dalam arti bahwa kita dapat menggambarkan komputer untuk ditiru komputer dan komputer akan menirunya. Untuk banyak contoh, cari "mesin virtual".

Dimungkinkan untuk membuat Mesin Universal Turing - TM yang menerima deskripsi TM lain kemudian mengemulasi operasi TM itu pada input yang disediakan.

$n$$2^{2^n}$

Untuk titik awal pada literatur, saya dapat merekomendasikan " Tentang Keberadaan Universal Finite atau Pushdown Automata ", yang mempelajari tidak adanya automata universal. Anda mungkin juga melihat referensi (dan sebagainya).

Apa yang membuat mesin Turing istimewa adalah bahwa walaupun sangat, sangat sederhana, ia dapat menjalankan semua (kelas) algoritma yang dapat kita pikirkan. Tidak ada mesin yang dikenal yang lebih kuat (dalam hal itu dapat menjalankan algoritma, mesin Turing tidak mampu).

Menjadi sederhana secara mekanis, mudah untuk menunjukkan apakah, atau pada tingkat mana, mesin lain setara dengan mesin Turing. Ini pada gilirannya membuatnya relatif mudah untuk menunjukkan apakah komputer yang diberikan (atau bahasa komputer) benar-benar universal (c / f "Turing-complete").

Mengapa model automata terbatas tidak cukup?

Sementara jawaban lain telah menyebutkan banyak aspek yang relevan, saya percaya bahwa kelebihan utama mesin Turing dibandingkan automata terbatas adalah pemisahan data dan program . Ini memungkinkan Anda untuk menganalisis program yang cukup terbatas dan membuat pernyataan tentang bagaimana program itu akan menangani input yang berbeda, tanpa membatasi ukuran input.

Meskipun secara teori dimungkinkan untuk menggambarkan komputer yang sebenarnya dan sesuatu seperti mesin Turing dengan pita hingga sebagai mesin keadaan, itu tidak benar-benar layak: jumlah negara adalah eksponensial dalam jumlah memori yang dimiliki mesin Anda, dan terbatas pada umumnya. formalisme otomat negara mengharuskan Anda untuk secara eksplisit mendaftar transisi antara negara-negara ini. Jadi untuk otomat keadaan terbatas umum sebesar itu cukup tidak mungkin untuk melakukan pengurangan berdasarkan pada enumerasi penuh semua transisi keadaan.

Tentu saja, di komputer nyata, menyatakan transisi tidak dapat terjadi secara sewenang-wenang. Tidak ada perintah untuk menukar sepertiga bit dalam memori dalam satu langkah perhitungan. Jadi, Anda bisa mencoba membuat spesifikasi yang lebih ringkas untuk transisi keadaan. Sesuatu seperti spesifikasi set instruksi arsitektur Anda. Tentu saja, arsitektur komputer sungguhan rumit untuk kinerja, sehingga Anda dapat menyederhanakan ini lebih jauh, ke beberapa set instruksi yang sangat sederhana, yang hanya melakukan langkah-langkah yang sangat kecil menggunakan input dan output yang sangat terbatas. Pada akhirnya Anda mungkin menemukan bahwa arsitektur Anda menyerupai sesuatu seperti juru mesin Turing: menggunakan beberapa bit kode program dan satu bit input, menghasilkan sedikit output dan bergerak dalam kode program Anda.

Salah satu alternatif akan menggunakan keadaan otomat keadaan terbatas hanya untuk mewakili data yang sedang diproses oleh program, sementara menyandikan program itu sendiri ke dalam transisi keadaan. Itu akan memerlukan masalah yang sama tentang bagaimana cara menghitung semua keadaan, dan representasi yang kompak mungkin akan mendekati apa yang dilakukan mesin Turing.

Apa gunanya mempelajari model yang jauh lebih kuat ini sehubungan dengan komputer nyata?

Secara keseluruhan saya akan mengatakan bahwa mesin Turing terbatas-tape mungkin akan menjadi model yang lebih baik untuk komputer yang sebenarnya. Tetapi untuk banyak pertanyaan ilmiah, perbedaan antara pita yang terbatas tetapi besar dan tak terbatas tidak relevan, jadi hanya mengklaim pita tak terbatas membuat segalanya lebih mudah. Untuk pertanyaan lain, jumlah kaset yang digunakan adalah inti dari pertanyaan, tetapi model tersebut dengan mudah memungkinkan Anda untuk berbicara tentang jumlah penggunaan kaset tanpa perlu repot menentukan apa yang terjadi jika perhitungan kehabisan kaset.

Sebagian besar masalah membutuhkan mesin Turing ukuran terbatas

Meskipun mengasumsikan tape tidak terikat adalah penyederhanaan yang berguna, sebagian besar masalah / algoritma sebenarnya membutuhkan jumlah kaset yang terbatas, dan batas-batas memori yang diperlukan (mungkin tergantung pada ukuran input) dapat dianalisis dan sering terbukti.

Ini juga sering digeneralisasi ke jenis komputer lain (yang analisis atau bukti terikatnya mungkin jauh lebih berantakan daripada pada mesin Turing), dan memungkinkan untuk memperkirakan jumlah penyimpanan sementara yang diperlukan untuk masalah tertentu - dapatkah itu dilakukan dalam jumlah tetap ruang? Proporsional dengan input? Apakah ini membutuhkan jumlah ruang yang eksponensial saat input tumbuh?

Salah satu fitur penting dari mesin turing yang automata terbatas tidak berbagi adalah bahwa mereka dapat skala jumlah memori yang dibutuhkan untuk memecahkan masalah dengan ukuran masalah .

$n$$n\cdot2$

Intinya: banyak masalah memiliki solusi alami yang menggunakan lebih banyak memori, semakin besar masalahnya. Jadi, wajar untuk menggambarkan solusi ini dengan representasi yang dapat menggunakan memori tak terbatas - bukan karena satu contoh akan menggunakan jumlah tak terbatas itu, tetapi karena ada contoh yang menggunakan setiap jumlah. Anda dapat melakukannya dengan mesin turing, tetapi juga dengan urutan automata terbatas.

Komputer nyata memiliki memori yang terbatas dan hanya sejumlah negara terbatas. Jadi mereka pada dasarnya automata terbatas.

Mesin Turing adalah turunan dari automata terbatas. Mesin Turing praktis adalah arsitektur von Nuemann.