Teori komputasi adalah cabang ilmu komputer dan matematika yang membahas apakah dan bagaimanakah suatu masalah dapat dipecahkan pada model komputasi, menggunakan algoritma.
Bidang ini dibagi menjadi dua cabang: teori komputabilitas dan teori
kompleksitas, namun kedua cabang berurusan dengan model formal
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 meisn Turing dapat dipecahkan oleh komputer yang memiliki jumlah
memori terbatas.
Sumber :: http://istanateknologi.blogspot.co.id/2015/04/pengertian-komputasi-dan-teori-komputasi.html
Tidak ada komentar:
Posting Komentar