Turing kekuatan komputasional dan lengkap

Dalam sebuah ceramah seorang profesor menyebutkan bahwa komputer modern tidak memiliki kekuatan komputasi sebanyak mesin Turing karena mereka tidak memiliki memori tak terbatas, dan karena tidak ada komputer yang dapat memiliki memori tak terbatas, mesin Turing karenanya tidak dapat dicapai dan hanya mewakili batas atas komputasi. Adakah ukuran, atau definisi masalah apa (atau kelas masalah) yang berada di luar jangkauan daya komputasi kita karena hal ini?

Jika kita menganggap alam semesta sebagai terbatas, maka segala sesuatu yang membutuhkan lebih banyak memori daripada jumlah terbatas itu berada di luar kemampuan komputasi kita.

Namun ini bukan model yang baik untuk mempelajari komputasi, model mesin Turing bekerja jauh lebih baik dalam kenyataan dan itulah alasan kami menggunakannya untuk mempelajari komputasi pada komputer nyata. Mesin Turing tidak benar-benar membutuhkan jumlah memori yang tak terbatas, ia hanya membutuhkan jumlah memori yang tidak terbatas . Misalnya, kami dapat memberikan memori tambahan ke komputer seiring waktu (karena komputer membutuhkan lebih banyak memori) dan kemudian kami memiliki sesuatu yang mirip dengan mesin Turing. Jika kita berasumsi bahwa kita memiliki jumlah waktu dan memori yang tidak terbatas untuk menyelesaikan perhitungan kita maka mesin Turing menangkap konsep kemampuan komputasi ini secara prinsip dengan cukup baik.

Lihat artikel Wikipedia tentang mesin Turing, ada bagian yang membahas relevansi model.

Jika Anda tertarik pada kemampuan komputasi yang layak , maka teori kompleksitas (di mana kami mempertimbangkan berbagai jumlah sumber daya seperti waktu dan ruang untuk melakukan tugas komputasi) lebih dekat dengan apa yang benar-benar dapat kita lakukan dalam praktik daripada teori komputabilitas. Banyak ahli menyatakan bahwa perhitungan yang layak termasuk dalam kelas kompleksitas (dan yang lebih baru dalam versi probabilistik dan kuantum P , yaitu B P P dan B Q P ).$\mathsf{P}$$\mathsf{P}$$\mathsf{BPP}$$\mathsf{BQP}$

Anda mungkin mempertimbangkan Linear Bounded Automaton dan bahasa yang sesuai adalah bahasa yang peka konteks . Lihat Chomsky Hierarchy untuk mengetahui bahasa mana yang di luar jangkauan automata tersebut.

btw, dalam beberapa hal, beberapa masalah "tak terjangkau" sekarang menjadi dalam jangkauan, karena daya komputasi yang terbatas!

Misalnya, Menghentikan Masalah untuk Mesin Turing tidak dapat diputuskan, tetapi itu dapat ditentukan untuk Linear Bounded Automata.

Teori komputasi adalah abstraksi dari dunia nyata. Dalam banyak hal, abstraksi itu tidak cocok untuk dunia nyata. Untuk satu, kita tidak dapat membuat komputer dengan memori tidak terbatas; jadi kami bahkan tidak bisa membuat mesin untuk mengenali bahasa reguler yang sewenang-wenang - atau bahkan bahasa yang terbatas sembarang!

Namun ternyata ini bukan masalah yang terlalu besar; di dunia nyata, kita bahkan tidak bisa membangun input dari ukuran sembarang, dan bahkan jika kita bisa, kita tidak akan cukup lama untuk melihat jawabannya.

Maka, dalam arti yang ketat, tidak: kelas komputer yang dapat disadari secara fisik benar-benar kurang kuat daripada kelas mesin Turing. Ini benar-benar kurang kuat daripada kelas automata terbatas, juga.