Apakah PC kami berfungsi sebagai Mesin Turing?

Apakah PC kami berfungsi sebagai Mesin Turing? Model Mesin Turing terdiri dari pita memori tak terbatas, yang berarti status tak terbatas. Tapi anggaplah jika PC kita memiliki 128 MB memori dan 30GB disk itu akan memiliki 256 ^ 30128000000 negara dan dengan demikian, ia memiliki status yang terbatas.

Saya tahu bahwa kita dapat menulis jenis program yang, jika selama eksekusi kita kehabisan memori, akan meminta untuk menukar disk memori dengan disk memori kosong dan melanjutkan eksekusi.

Tetapi bagaimana jika kita tidak menukar disk memori, dalam hal ini apakah benar untuk menganggap PC sebagai FA ?

Anda benar bahwa komputer fisik memiliki memori yang terbatas sehingga tidak Turing-lengkap. Ada beberapa cara lain di mana teori komputasi bukanlah model yang baik untuk komputasi - tidak memperhitungkan waktu dan kendala memori. Teori kompleksitas ditemukan (mungkin) sebagai penggambaran komputasi yang lebih realistis, tetapi IMHO menderita masalah yang serupa (tetapi lebih halus).

Di sisi lain, untuk mempelajari kemampuan dan batasan komputasi secara matematis, kita perlu menggunakan beberapa abstraksi yang tidak dibatasi. Itu memungkinkan analisis. Demikian pula, dalam mekanika statistik kita mengasumsikan bahwa jumlah elemen (atom atau molekul) sangat besar, sehingga perilakunya mendekati batas (yaitu, kita membiarkan jumlah elemen cenderung tak terhingga). Mempelajari komputasi dari perspektif asimptotik memiliki kelebihan yang serupa, tetapi terkadang menyesatkan. Berikut adalah beberapa contoh yang terakhir:

1. Dalam kriptografi, algoritma eksponensial kadang-kadang layak. Jika kita memilih parameter keamanan yang salah, enkripsi kita mungkin tidak aman meskipun "terbukti aman".
2. Algoritma polinomial-waktu dianggap mewakili komputasi yang efisien dan layak, tetapi banyak dari mereka tidak layak. Sebagai contoh, kebanyakan algoritma penggandaan matriks yang canggih tidak digunakan dalam praktiknya.
3. Teori kompleksitas modern terobsesi dengan kinerja kasus terburuk, dan tidak dapat menganalisis algoritma heuristik yang digunakan dalam praktik. Masalah NP-hard dianggap tidak layak, namun mereka dipecahkan dalam praktik sepanjang waktu.

Masalah terpisah adalah bahwa komputer sungguhan sama sekali tidak bekerja seperti mesin Turing. Mereka bekerja seperti mesin RAM, yang merupakan abstraksi yang lebih baik untuk komputasi yang sebenarnya.

Saya pikir Anda sudah memberikan jawabannya sendiri. Jika aspek utama yang Anda khawatirkan adalah keadaan negara (dalam), maka Mesin Turing hanya ada sebagai "perangkat hipotetis".

Tidak peduli berapa banyak memori yang akan Anda berikan pada PC Anda, itu akan selalu terbatas, maka Anda dapat menemukan program yang akan berjalan pada Mesin Turing "nyata", tetapi tidak pada PC ini karena pita terikat.

http://en.wikipedia.org/wiki/Turing_machine#Comparison_with_real_machines

Pada saat mesin Turing ditemukan, komputer adalah wanita yang akan melakukan perhitungan pada kertas bekas. Itulah pengertian komputasi yang diekspresikan oleh mesin Turing. Rekaman mereka bukan bagian dari mereka sama seperti kertas bekas adalah bagian dari seseorang yang melakukan perhitungan.

Ini masih merupakan model yang baik untuk perhitungan berbasis komputer karena batas-batas pada sumber daya di komputer biasanya cukup besar. Model perhitungan yang terbatas secara inheren hanya menjadi berguna ketika jumlah keadaan yang mungkin sangat kecil.

Komputer modern adalah Turing lengkap, umumnya istilah ini digunakan dengan pengecualian perangkat penyimpanan tak terbatas. Dalam praktiknya, ingatannya bisa cukup lama. Sebagai contoh, seiring dengan menjadi penduga fungsi universal, jaringan saraf berulang dengan memori (dan berjalan berulang kali) dikatakan Turing lengkap. Memang, Mesin Neural Turing membawa ide ini ke tahap lebih lanjut dengan menyimpulkan algoritma sederhana.