Teori komputasi: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Rescuing 0 sources and tagging 1 as dead.) #IABot (v2.0.8 |
Tidak ada ringkasan suntingan |
||
Baris 1:
[[Berkas:Maquina.png|jmpl|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 [[
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> 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]]).<ref>{{cite video | last = Rabin | first = Michael O. | author-link = Michael O. Rabin | title = Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View (Turing, Church, Gödel, Komputabilitas, Kompleksitas, dan Keacakan: Pandangan Individu)| date = June 2012 | url = http://videolectures.net/turing100_rabin_turing_church_goedel/ }}</ref> It might seem that the potentially infinite memory capacity is an unrealizable attribute, but any [[Decidability (logic)|decidable]] problem<ref name=Monk1976>{{cite book |author =Donald Monk |year =1976 |title =Mathematical Logic (Logika Matematis) |publisher =Springer-Verlag |isbn =9780387901701 |url-access =registration |url =https://archive.org/details/mathematicallogi00jdon }}</ref> 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, [[Logika matematika|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 ===
{{main|Teori Automata}}
{| class="wikitable"
|-
! Tata Bahasa
! Bahasa
! Otomat
! Peraturan Produksi (batas-batas)
|-
| Type-0
| [[Bahasa Terhitung Rekursif|Terhitung secara Rekursif]]
| [[Mesin Turing]]
| <math>\alpha \rightarrow \beta</math> (tidak ada batasan)
|-
| Type-1
| [[Tata bahasa Berkonteks Sensitif|Konteks Sensitif]]
| [[Linear Terikat Otomat|Mesin Turing yang Terikat Linear dan Tak Dapat Ditentukan]]
| <math>\alpha A \beta \rightarrow \alpha \gamma \beta</math>
|-
| Type-2
| [[Tata bahasa tanpa konteks|Tanpa Konteks]]
| Tak dapat ditentukan [[Penekanan Otomat]]
| <math>A \rightarrow \gamma</math>
|-
| Type-3
| [[Tata bahasa Reguler|Regular]]
| [[Keadaan Otomat Terbatas]]
| <math>A \rightarrow a</math><br /> dan <br /><math>A \rightarrow aB</math>
|}
▲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 ==
| |||