Teori Komputasi

Teori komputasi merupakan cabang ilmu komputer dan matematika yang digunakan untuk menemukan apakah dan bagaimanakah suatu masalah dapat dipecahkan pada model komputasi menggunakan algoritma. Teori komputasi dibagi menjadi 3, yaitu :

1.        Teori Otomata (automata theory)  
        mengacu pada definisi dan sifat-sifat model komputasi.

2.        Teori Komputabilitas (computability theory)  
      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).

3.        Teori Kompleksitas (computational complexity theory)  
      bertujuan untuk mengkaji kebutuhan waktu dan ruang untuk memecahkan persoalan yang diselesaikan dengan pendekatan yang berbeda-beda. Dengan kata lain, teori kompleksitas mengklasifikasikan persoalan sebagai persoalan mudah (easy) atau persoalan sukar (hard).

Beberapa model komputasi :

• Finite State Automata (FSA)/Finite State Machine (FSM)
• Push Down Automata (PDA)
• Mesin Turing (Turing Machine) atau TM

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. 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.