STUDI KASUS TEORI KOMPUTASI
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. Bidang teori komputasi dibagi menjadi tiga cabang besar: teori automata dan bahasa formal, teori komputabilitas dan teori kompleksitas komputasional, dimana dihubungkan dengan pertanyaan: "Apa saja kemampuan dan batasan yang dimiliki komputer?". Untuk melakukan studi komputasi dengan ketat, ilmuwan komputer bekerja dengan abstraksi matematika dari komputer yang dinamakan model komputasi. Ada beberapa model yang digunakan, tetapi yang paling umum dipelajari adalah mesin Turing. Para ilmuwan mempelajari mesin Turing karena mudah untuk diformulasikan, bisa di analisa dan digunakan untuk membuktikan sebuah hasil, dan karena mesin Turing merepresentasikan model komputasi yang kuat dan ...