Teori komputasi: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8 |
Rescuing 0 sources and tagging 1 as dead.) #IABot (v2.0.8 |
||
Baris 2:
'''Teori komputasi''' adalah cabang [[ilmu komputer]] dan [[matematika]] yang membahas apakah dan bagaimanakah suatu masalah dapat dipecahkan pada [[model komputasi]], menggunakan [[algoritme]]. Bidang ilmu ini terutama membahas hal terkait komputabilitas dan kompleksitas, dalam kaitannya dengan formalisme komputasi.<ref>{{Cite web|url=https://www.geeksforgeeks.org/introduction-of-theory-of-computation/|title=Introduction of Theory of Computation|date=2017-11-13|website=GeeksforGeeks|language=en-US|access-date=2020-08-04}}</ref><ref>{{Cite web|url=http://www.contrib.andrew.cmu.edu/~hebah/Theory%20of%20computation.html|title=Theory of Computation|website=www.contrib.andrew.cmu.edu|access-date=2020-08-04}}</ref>
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]].<ref>{{Cite web|url=https://www.britannica.com/technology/Turing-machine|title=Turing machine {{!}} Definition & Facts|website=Encyclopedia Britannica|language=en|access-date=2020-08-04}}</ref><ref>{{Cite book|url=https://plato.stanford.edu/archives/win2019/entriesuring-machine/|title=The Stanford Encyclopedia of Philosophy|last=De Mol|first=Liesbeth|date=2019|publisher=Metaphysics Research Lab, Stanford University|editor-last=Zalta|editor-first=Edward N.|edition=Winter 2019}}{{Pranala mati|date=April 2021 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> 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.
== Referensi ==
| |||