Teori komputasi adalah cabang ilmu komputer dan matematika yang membahas apakah dan bagaimanakah suatu masalah dapat dipecahkan pada model komputasi, menggunakan algoritma. Bidang ini dibagi menjadi dua cabang: teori komputabilitas dan teori kompleksitas, namun kedua cabang berurusan dengan model formal komputasi.
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. Sebuah mesin Turing dapat dipikirkan sebagai komputer pribadi meja dengan kapasitas memori yang tak terhingga, namun 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, 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.
Implementasi Komputasi Pada Bidang Matematika
Implementasi komputasi terdapat diberbagai bidang, diantaranya : fisika, kimia, matematika, ekonomi, geologi, dan geografi. Dalam pembahasan ini akan membahas implementasi komputasi pada bidang matematika.
Implementasi komputasi modern di bidang matematika ada numerical analysis yaitu sebuah algoritma dipakai untuk menganalisa masalah - masalah matematika. Bidang analisis numerik sudah sudah dikembangkan berabad-abad sebelum penemuan komputer modern. Interpolasi linear sudah digunakan lebih dari 2000 tahun yang lalu. Banyak matematikawan besar dari masa lalu disibukkan oleh analisis numerik, seperti yang terlihat jelas dari nama algoritma penting seperti metode Newton, interpolasi polinomial Lagrange, eliminasi Gauss, atau metode Euler.
Buku-buku besar berisi
rumus dan tabel data seperti interpolasi titik dan koefisien fungsi diciptakan
untuk memudahkan perhitungan tangan. Dengan menggunakan tabel ini (seringkali
menampilkan perhitungan sampai 16 angka desimal atau lebih untuk beberapa
fungsi), kita bisa melihat nilai-nilai untuk diisikan ke dalam rumus yang
diberikan dan mencapai perkiraan numeris sangat baik untuk beberapa fungsi.
Karya utama dalam bidang ini adalah penerbitan NIST yang disunting
oleh Abramovich dan
Stegun, sebuah buku setebal 1000 halaman lebih. Buku ini berisi
banyak sekali rumus yang umum digunakan dan fungsi dan nilai-nilainya di banyak
titik. Nilai f-nilai fungsi tersebut tidak lagi terlalu berguna ketika komputer
tersedia, namun senarai rumus masih mungkin sangat berguna.
Kalkulator
mekanik juga dikembangkan sebagai alat untuk perhitungan tangan.
Kalkulator ini berevolusi menjadi komputer elektronik pada
tahun 1940. Kemudian ditemukan bahwa komputer juga berguna untuk tujuan
administratif. Tetapi penemuan komputer juga mempengaruhi bidang analisis
numerik, karena memungkinkan dilakukannya perhitungan yang lebih panjang dan
rumit.
Sumber :
http://id.wikipedia.org/wiki/Teori_komputasi
http://livemakefun.blogspot.com/2014/03/perkembangan-teori-komputasi-modern_16.html
