Teori komputasi

Teori komputasi adalah cabang ilmu komputer dan matematika yang membahas apakah dan bagaimanakah suatu masalah dapat dipecahkan pada model komputasi, menggunakan algoritma. Bidang ilmu ini terutama membahas hal terkait komputabilitas dan kompleksitas, dalam kaitannya dengan formalisme komputasi.^[1][2] Bidang teori komputasi dibagi menjadi tiga cabang besar: teori automata dan bahasa formal, teori komputabilitas dan teori kompleksitas komputasional, dimana dihubungkan dengan pertanyaan: "Apa saja kemampuan dan batasan yang dimiliki komputer?".^[3]

Untuk melakukan studi komputasi dengan ketat, ilmuwan komputer bekerja dengan abstraksi matematika dari komputer yang dinamakan model komputasi. Ada beberapa model yang digunakan, tetapi yang paling umum dipelajari adalah mesin Turing.^[4][5] Para ilmuwan mempelajari mesin Turing karena mudah untuk diformulasikan, bisa di analisa dan digunakan untuk membuktikan sebuah hasil, dan karena mesin Turing merepresentasikan model komputasi yang kuat dan "cocok" (lihat Church–Turing thesis).^[6] Hal ini sepertinya memiliki potensial kapasitas memori tak terhingga merupakan atribut yang tak disadari, tetapi pada tiap permasalahan logika^[7] diselesaikan oleh mesin Turing selalu membutuhkan memori yang terbatas. Sehingga, dalam prinsipnya setiap permasalahan yang bisa diselesaikan (dipilih untuk diselesaikan) oleh mesin Turing bisa diselesaikan oleh komputer ynag memiliki memori yang terbatas. Sebuah mesin Turing dapat dipikirkan sebagai komputer pribadi meja dengan kapasitas memori yang tak terhingga, tetapi hanya dapat diakses dalam bagian-bagian terpisah dan diskret. Ilmuwan komputer mempelajari mesin Turing karena mudah dirumuskan, dianalisis dan digunakan untuk pembuktian, dan karena mesin ini mewakili model komputasi yang dianggap sebagai model paling masuk akal yang paling ampuh yang dimungkinkan. Kapasitas memori tidak terbatas mungkin terlihat sebagai sifat yang tidak mungkin terwujudkan, tetapi setiap permasalahan yang "terputuskan" (decidable) yang dipecahkan oleh mesin Turing selalu hanya akan memerlukan jumlah memori terhingga. Jadi pada dasarnya setiap masalah yang dapat dipecahkan (diputuskan) oleh meisn Turing dapat dipecahkan oleh komputer yang memiliki jumlah memori terbatas.

1. ^ "Introduction of Theory of Computation". GeeksforGeeks (dalam bahasa Inggris). 2017-11-13. Diakses tanggal 2020-08-04. 
2. ^ "Theory of Computation". www.contrib.andrew.cmu.edu. Diakses tanggal 2020-08-04. 
3. ^ Michael Sipser (2013). Introduction to the Theory of Computation 3rd (Pengenalan Teori Komputasi). Cengage Learning. ISBN 978-1-133-18779-0. central areas of the theory of computation: automata, computability, and complexity. (Page 1) 
4. ^ "Turing machine | Definition & Facts". Encyclopedia Britannica (dalam bahasa Inggris). Diakses tanggal 2020-08-04. 
5. ^ De Mol, Liesbeth (2019). Zalta, Edward N., ed. The Stanford Encyclopedia of Philosophy (edisi ke-Winter 2019). Metaphysics Research Lab, Stanford University. ^{[pranala nonaktif permanen]}
6. ^ Rabin, Michael O. (June 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View (Turing, Church, Gödel, Komputabilitas, Kompleksitas, dan Keacakan: Pandangan Individu). 
7. ^ Donald Monk (1976). Mathematical Logic (Logika Matematis). Springer-Verlag. ISBN 9780387901701.