Teori komputasi

Representasi artistik dari mesin Turing. Mesin Turing biasanya digunakan sebagai model teoritis untuk 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.^[1]^[2] 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?".^[3]

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.^[4]^[5] 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 "cocok" (lihat Church–Turing thesis).^[6] Hal ini sepertinya memiliki potensial kapasitas memori tak terhingga merupakan atribut yang tak disadari, tetapi pada tiap permasalahan logika^[7] diselesaikan oleh mesin Turing selalu membutuhkan memori yang terbatas. Sehingga, dalam prinsipnya setiap permasalahan yang bisa diselesaikan (dipilih untuk diselesaikan) oleh mesin Turing bisa diselesaikan oleh komputer ynag memiliki memori yang terbatas. Sebuah mesin Turing dapat dipikirkan sebagai komputer pribadi meja dengan kapasitas memori yang tak terhingga, tetapi 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, tetapi 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.

Sejarah

Teori komputasi bisa dijadikan penciptaan sebuah model dari seluruh bidang ilmu komputer. Maka, matematika dan logika digunakan. Pada abad terakhir, teori komputasi dijadikan menjadi ilmu akademis disiplin yang terpisah dari matematika.

Beberapa pioner atau ilmuwan terkenal dari teori komputasi adalah Ramon Llull, Alonzo Church, Kurt Gödel, Alan Turing, Stephen Kleene, Rózsa Péter, John von Neumann, dan Claude Shannon.

Cabang

Teori Automata

Tata Bahasa	Bahasa	Otomat	Peraturan Produksi (batas-batas)
Type-0	Terhitung secara Rekursif	Mesin Turing	$\alpha \rightarrow \beta$ (tidak ada batasan)
Type-1	Konteks Sensitif	Mesin Turing yang Terikat Linear dan Tak Dapat Ditentukan	$\alpha A\beta \rightarrow \alpha \gamma \beta$
Type-2	Tanpa Konteks	Tak dapat ditentukan Penekanan Otomat	$A\rightarrow \gamma$
Type-3	Regular	Keadaan Otomat Terbatas	$A\rightarrow a$ dan $A\rightarrow aB$

Teori Automata adalah ilmu tentang mesin abstrak (atau lebih tepatnya adalah sistem atau mesin abstrak 'matematis') dan permasalahan komputasional yang bisa diselesaikan oleh mesin-mesin ini. Mesin-mesin abstrak ini disebut sebagai automata. Automata (Αυτόματα) berarti sesuatu yang melakukan sesuatu dengan sendirinya. Teori Automata sangat dekat dengan teori bahasa formal,^[8] Automata sering diklasifikasikan oleh beberapa kelas dari bahasa formal karena mereka memiliki kemampuan untuk "mengenal". Sebuah Automaton bisa merupakan representasi bahasa formal yang terbatas yang bisa merupakan himpunan tak terbatas. Automata digunakan sebagai model teoritis untuk mesin komputasi, dan digunakan untuk kemampuan komputabilitas.

Teori Bahasa Formal

Inklusi Himpunan yang dideskripsikan pada Hierarki Chomsky

Teori Bahasa adalah cabang dari matematika yang mempelajari tentang menerangkan bahasa-bahasa sebagai bagian dari operasi-operasi atas Alfabet(bahasa formal). Teori ini sangat dekat dengan teori Automata, karena Automata digunakan untuk membuat dan mengenal bahasa formal. Terdapat beberapa kelas dari bahasa formal, tiap-tiapnya membolehkan spesifikasi pada bahasa kompleks daripada satunya sebelum itu (Hierarki Chomsky),^[9] dan tiap korespondensi kepada sebuah kelas dari Automata yang mengenalnya. Karena Automata digunakan sebagai model-model dari komputasi, bahasa formal lebih disarankan sebagai mode spesifikasi untuk semua permasalahan yang harus di komputasi.

Teori Komputabilitas

Teori Komputabilitas berhubungan secara pokok dengan pertanyaan-pertanyaan dari batas cakupan pada dimana sebuah masalah itu dapat diselesaikan oleh sebuah komputer. Pernyataan bahwa permasalahan terbata-bata tak bisa diselesaikan oleh mesin Turing^[10] Adalah salah satu hasil terpenting pada teori komputabilitas, karena hal itu merupakan contoh dari permasalahan konkret yang sama-sama mudah untuk diformulasikan dan tak mungkin diselesaikan oleh mesin Turing. Terlebih pada teori komputabilitas yang membangun dari hasil permasalahan terbata-bata.

Langkah lain dalam teori komputabilitas adalah Teorema Rice, dimana menyebutkan bahwa pada semua properti dari fungsi non-trivial, adalah logika diantara pada mesin Turing mengkomputasi fungsi parsial dengan properti itu.^[11]

Teori Komputabilitas lebih dekat pada percabangan dari logika matematis disebut teori rekursi, dimana menghapus batasan dari pembelajaran model komputasi yang dimana bisa disederhanakan hingga model Turing.^[12] Banyak matematikawan dan ahli teori komputasional yang mempelajari pembelajaran teori rekursi akan merujuk hal itu pada teori komputasi.