Menurut situs wikipedia 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.
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