Teori komputasi: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Tidak ada ringkasan suntingan |
Tidak ada ringkasan suntingan Tag: kemungkinan perlu pemeriksaan terjemahan |
||
Baris 2:
'''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.<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>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?".''<ref name=Sipser-3rd>{{cite book|author = Michael Sipser | year = 2013 | title = Introduction to the Theory of Computation 3rd (Pengenalan Teori Komputasi) |quote=central areas of the theory of computation: automata, computability, and complexity. (Page 1) |publisher =Cengage Learning |isbn=978-1-133-18779-0| author-link = Michael Sipser }}</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> 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>
== Sejarah ==
Baris 40:
| <math>A \rightarrow a</math><br /> dan <br /><math>A \rightarrow aB</math>
|}
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]],<ref name=hopcroft-ullman>{{cite book|author =[[John Hopcroft|Hopcroft, John E.]] and [[Jeffrey D. Ullman]] | year = 2006| title =Introduction to Automata Theory, Languages, and Computation. (Pengenalan Teori Automata, Bahasa, dan Komputasi) 3rd ed| publisher =Reading, MA: Addison-Wesley. |isbn= 978-0-321-45536-9| title-link = Introduction to Automata Theory, Languages, and Computation (Pengenalan Teori Automata, Bahasa, dan Komputasi)}}</ref> 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 ====
{{main|Formal language}}
[[Image:Chomsky-hierarchy.svg|thumb|right|200px|alt=Hierarki Chomsky|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),<ref>{{cite journal |last=[[Chomsky hierarchy]] |date=1956 |title=Tiga Model untuk Mendeskripsikan dari sebuah Bahasa |journal=Information Theory, IRE Transactions on |publisher=IEEE |volume=2 |issue=3 |pages= 113–124|doi=10.1109/TIT.1956.1056813 }}</ref>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 ===
{{main|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<ref>{{cite journal |last=[[Alan Turing]] |date=1937 |title=(Dalam bilangan-bilangan yang dapat dikomputasi, dengan sebuah pengaplikasian dalam permasalahan Entscheidung) On computable numbers, with an application to the Entscheidungsproblem |url=http://www.turingarchive.org/browse.php/B/12 |journal= Proceedings of the London Mathematical Society |publisher=IEEE |volume=2 |issue=42 |pages=230–265 |doi=10.1112/plms/s2-42.1.230 |s2cid=73712 |access-date=11 Oktober 2022}}</ref>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.<ref>{{cite journal |last=Henry Gordon Rice |date=1953 |title=Classes of Recursively Enumerable Sets and Their Decision Problems (Kelas-kelas Himpunan Enumerasi Rekursif dan Permasalahan Pemilihannya) |journal= Transactions of the American Mathematical Society |publisher=American Mathematical Society|volume=74 |issue=2 |pages=358–366 |doi= 10.2307/1990888|jstor=1990888|doi-access=free }}</ref>
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.<ref name=davis>{{cite book|author =Martin Davis |year = 2004 |title = (Yang Tak Bisa Ditentukan: Kertas Dasar pada Proposisi Yang Tak Dapat Ditentukan, Permasalahan Yang Tak Dapat Diselesaikan dan fungsi komputasi) The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed) |publisher =Dover Publications |isbn=978-0486432281|author-link = Martin Davis (mathematician) }}</ref> Banyak matematikawan dan ahli teori komputasional yang mempelajari pembelajaran teori rekursi akan merujuk hal itu pada teori komputasi.
=== Teori Komputasional Kompleks ===
| |||