Ilmu komputer teoretis
Sejarah

Pada tahun 1931, Kurt Gödel memublikasikan teorema ketidaklengkapan yang membuktikan bahwa terdapat batasan mendasar dalam inferensi logika dan pembuktian matematika, atau dalam kata lain, terdapat keterbatasan logika dan matematika dalam melakukan penyangkalan atau pembuktian matematika.
Kajian mengenai teori informasi dimulai kemudian dengan publikasi teori matematika pada proses komunikasi digital pada tahun 1948 oleh Claude Shannon. Pada dekade yang sama, Donald Hebb memperkenalkan model matematis yang menggambarkan proses biologis aktivitas pembelajaran di otak manusia. Hipotesis Hebb tersebut didukung oleh banyaknya data biologis dari penelitian-penelitian mengenai jaringan syaraf. Dari penelitian-penelitian tersebut, mulai dikenal kajian jaringan saraf tiruan dan pemrosesan terdistribusi paralel. Pada tahun 1971, Stephen Cook dan Leonid Levin secara independen membuktikan bahwa terdapat permasalahan matematika yang bersifat NP-complete – sebuah hasil penting dalam kajian teori kompleksitas komputasi.
Pada awal abad ke-20, perkembangan pesat kajian mekanika kuantum memberikan sudut pandang baru dalam pemaknaan kata "komputasi". Kajian teori informasi pada dekade sebelumnya fokus melakukan abstraksi terhadap kondisi realitas untuk mendapatkan informasi secara akurat, dengan mengabaikan bentuk fisik (aliran sinyal listrik pada prosesor, misalnya) dari mesin dan realitas itu sendiri. Kegiatan abstraksi ini bersandar pada prinsip-prinsip mekanika klasik yang menghasilkan informasi yang bermanfaat untuk kegiatan komunikasi maupun komputasi, contohnya pada mesin Turing.
Pada awal tahun 1980, beberapa peneliti menyadari bahwa prinsip-prinsip mekanika kuantum memiliki implikasi pada perspektif mengenai pemrosesan informasi. Fisikawan Feynman, Yuri Manin dan peneliti lain kemudian menemukan bahwa fenomena keterkaitan partikel tidak dapat disimulasikan dengan baik oleh mesin Turing, yang menggunakan bita 0 dan 1 dalam melakukan komputasi. Menggunakan fenomena ini, peneliti lain mencoba menggeser konsep "komputasi" yang menggunakan dua jenis bita digital: 0 dan 1, menjadi menggunakan qubit yang memiliki lebih dari dua "keadaan" (state) atau superposisi.
Dengan menggunakan komputasi dalam qubit, seseorang dapat melakukan komputasi pada fungsi dengan menggunakan beberapa "keadaan" secara bersamaan. Penemuan-penemuan ini mengangkat kajian terhadap konsep komputer kuantum pada paruh kedua abad ke-20. Salah satu kajian pada awal tahun 1990an yang dilakukan oleh Peter Shor meneliti suatu algoritma untuk memfaktorkan bilangan besar dalam kompleksitas waktu polinomial dengan memanfaatkan prinsip kuantum. Melalui penelusuran lebih lanjut, ditemukan bahwa algoritma ini berpotensi membuat algoritma kriptografi kunci publik seperti RSA menjadi tidak aman.
Kajian riset ilmu komputer teoretis modern didasarkan pada perkembangan-perkembangan dasar yang telah dibahas sebelumnya, namun juga mencakup ragam kajian matematika dan interdisipliner lain, seperti yang ditunjukkan di bawah ini:
| 0 | 1 | 2 | 3 | 4 | 5 |
| --- | --- | --- | --- | --- | --- |
|  P\rightarrow Q\, |  |  |  |  | P = NP ? |
| Logika matematika | Teori automata | Teori bilangan | Teori grafik | Teori komputasi | Teori kompleksitas komputasi |
| GNITIRW-TERCES |  \Gamma \vdash x:{\text{Int}} | </img> |  |  |  |
| Kriptografi | Teori tipe | Teori kategori | Geometri komputasi | Optimasi kombinatorial | Teori komputasi kuantum |