Pengertian tentang Teori Komputasi

Teori Komputasi adalah cabang ilmu komputer dan matematika yang membahas apakah dan bagaimanakah suatu masalah dapaet 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 bkerja dengan abstraksi matematika dari komputer yang dinamakan model komputasi . ada beberapa model yang di gunakan namun yang paling umum dipelajari adalaha mesin Turing . sebuah mesin turing dapat dipikirkan sebagai komputer pribadi meja dengan kapasitas memori yang tak terhingga , namun hanya dapat di akses dalam bagian-bagian terpisah dan diskret. Ilmuwan komputer mempelajari mesin turing karena mudah dirumuskan , dianalisis dan digunakan untuk pembuktian ,dan karena mesin ini mewakii model komputasi yang di anggap sebagai mode paling masuk akal yang paling ampih yang di mungkinkan. Kapasitas memri tidak terbatas munngkin terlihat sebagai sifat yang tidak munkin terwujudkan, namun setiap permasalahan yang "terputuskan"(decidable) yang dipecahkan oleh mesing Turing selalu hanya akan memerlukan jumlah memori terhingga. Jadi pada dasarnya setiap masalah yang dapa di pecahkan (diputuskan)oleh meson Turing dapa dipecahkan oleh komputer yang memiliki jumlah memori terbatas

sumber:
https://id.wikipedia.org/wiki/Teori_komputasi