TEORI KOMPUTASI
Teori komputasi (theory of computation) adalah cabang ilmu
komputer teoritis (theoritical computer science). Teori komputasi berkaitan
dengan studi bagaimana persoalan (problem) dapat diselesaikan pada sebuah model
dengan menggunakan algoritma. Model tersebut dinamakan model komputasi. Teori
komputasi dibagi lagi menjadi 3 ranting :
- Teori
Otomata (automata theory)
- Teori
Komputabilitas (computability theory)
- Teori
Kompleksitas (computational complexity theory)
Teori komputabilitas bertujuan untuk memeriksa apakah
persoalan komputasi dapat dipecahkan pada suatu model komputasi teoritis.
Dengan kata lain, teori komputabilitas mengklasifikasikan persoalan sebagai
dapat dipecahkan (solvable) atau persoalan yang tidak dapat dipecahkan
(unsolvable). Teori kompleksitas bertujuan untuk mengkaji kebutuhan waktu dan
ruang untuk memecahkan persoalan yang diselesaikan dengan pendekatan yang
berbeda-beda.