Teori komputasi merupakan dua cabang ilmu
yang dijadikan satu, yaitu komputer dan matematika untuk membahas bagaimana
sebuah masalah bisa dipecahkan dengan baik pada model komputasi yang
menggunakan algoritma.
Untuk melakukan studi komputasi dengan ketat,
ilmuwan komputer bekerja dengan abstraksi matematika dari komputer yang
dinamakan model komputasi. Ada beberapa model yang digunakan, namun yang paling
umum dipelajari adalah mesin turing. Sebuah mesin Turing dapat
dipikirkan sebagai komputer pribadi meja dengan kapasitas memori
yang tak terhingga, namun 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, namun 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 mesin turing dapat dipecahkan
oleh komputer yang memiliki jumlah memori terbatas.
Tidak ada komentar:
Posting Komentar