Teori komputasi - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T04:21:14Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 04.21
Baris 1:		Baris 1:
	'''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 (seni)\|formalisme]] komputasi. Bidang teori komputasi dibagi menjadi tiga cabang besar: [[teori automata]] dan [[bahasa formal]], [[teori komputabilitas]] dan [[teori kompleksitas komputasional]], di mana dihubungkan dengan pertanyaan: ''"Apa saja kemampuan dan batasan yang dimiliki komputer?".''		'''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 (seni)\|formalisme]] komputasi.<ref>[https://www.geeksforgeeks.org/introduction-of-theory-of-computation/ Introduction of Theory of Computation]. ''GeeksforGeeks''. 2017-11-13.</ref><ref>[http://www.contrib.andrew.cmu.edu/~hebah/Theory%20of%20computation.html Theory of Computation]. ''www.contrib.andrew.cmu.edu''.</ref> Bidang teori komputasi dibagi menjadi tiga cabang besar: [[teori automata]] dan [[bahasa formal]], [[teori komputabilitas]] dan [[teori kompleksitas komputasional]], di mana dihubungkan dengan pertanyaan: ''"Apa saja kemampuan dan batasan yang dimiliki komputer?".''<ref>Michael Sipser. ''Introduction to the Theory of Computation 3rd (Pengenalan Teori Komputasi)''. Cengage Learning. 2013. ISBN 978-1-133-18779-0.</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]]. Para ilmuwan mempelajari mesin Turing karena mudah untuk diformulasikan, bisa di analisis dan digunakan untuk membuktikan sebuah hasil, dan karena mesin Turing merepresentasikan model komputasi yang kuat dan "cocok" (lihat [[Church–Turing thesis]]). Hal ini sepertinya memiliki potensial kapasitas memori tak terhingga merupakan atribut yang tak disadari, tetapi pada tiap masalah logika diselesaikan oleh mesin Turing selalu membutuhkan memori yang terbatas. Sehingga, dalam prinsipnya setiap masalah yang bisa diselesaikan (dipilih untuk diselesaikan) oleh mesin Turing bisa diselesaikan oleh komputer yang 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 masalah 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.		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>[https://www.britannica.com/technology/Turing-machine Turing machine Definition & Facts]. ''Encyclopedia Britannica''.</ref><ref>Liesbeth De Mol. [https://plato.stanford.edu/archives/win2019/entriesuring-machine/ The Stanford Encyclopedia of Philosophy]. Metaphysics Research Lab, Stanford University. 2019.</ref> Para ilmuwan mempelajari mesin Turing karena mudah untuk diformulasikan, bisa di analisis dan digunakan untuk membuktikan sebuah hasil, dan karena mesin Turing merepresentasikan model komputasi yang kuat dan "cocok" (lihat [[Church–Turing thesis]]).<ref>Michael O. Rabin. [http://videolectures.net/turing100_rabin_turing_church_goedel/ Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View (Turing, Church, Gödel, Komputabilitas, Kompleksitas, dan Keacakan: Pandangan Individu)]. June 2012.</ref> Hal ini sepertinya memiliki potensial kapasitas memori tak terhingga merupakan atribut yang tak disadari, tetapi pada tiap masalah logika<ref>Donald Monk. [https://archive.org/details/mathematicallogi00jdon Mathematical Logic (Logika Matematis)]. Springer-Verlag. 1976. ISBN 9780387901701.</ref> diselesaikan oleh mesin Turing selalu membutuhkan memori yang terbatas. Sehingga, dalam prinsipnya setiap masalah yang bisa diselesaikan (dipilih untuk diselesaikan) oleh mesin Turing bisa diselesaikan oleh komputer yang 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 masalah 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 ==		== Sejarah ==
Baris 9:		Baris 9:

	== Cabang ==		== Cabang ==

	=== Teori Automata ===		=== 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>
			\|}

	Teori Automata adalah ilmu tentang mesin abstrak (atau lebih tepatnya adalah sistem atau mesin abstrak 'matematis') dan masalah 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 adalah ilmu tentang mesin abstrak (atau lebih tepatnya adalah sistem atau mesin abstrak 'matematis') dan masalah 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]], 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 teoretis untuk mesin komputasi, dan digunakan untuk kemampuan komputabilitas.		Teori Automata sangat dekat dengan teori [[bahasa formal]],<ref>Hopcroft, John E. and Jeffrey D. Ullman. ''Introduction to Automata Theory, Languages, and Computation. (Pengenalan Teori Automata, Bahasa, dan Komputasi) 3rd ed''. Reading, MA: Addison-Wesley. 2006. ISBN 978-0-321-45536-9.</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 teoretis untuk mesin komputasi, dan digunakan untuk kemampuan komputabilitas.

	==== Teori Bahasa Formal ====		==== Teori Bahasa Formal ====
			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>Chomsky hierarchy. ''Tiga Model untuk Mendeskripsikan dari sebuah Bahasa''. ''Information Theory, IRE Transactions on''. IEEE. 1956. Vol. 2 (3). hlm. 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 masalah yang harus di komputasi.

	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), 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 masalah yang harus di komputasi.

	=== Teori Komputabilitas ===		=== Teori Komputabilitas ===
			Teori Komputabilitas berhubungan secara pokok dengan pertanyaan-pertanyaan dari batas cakupan pada di mana sebuah masalah itu dapat diselesaikan oleh sebuah komputer. Pernyataan bahwa [[permasalahan terbata-bata]] tak bisa diselesaikan oleh mesin Turing<ref>Alan Turing. [http://www.turingarchive.org/browse.php/B/12 (Dalam bilangan-bilangan yang dapat dikomputasi, dengan sebuah pengaplikasian dalam permasalahan Entscheidung) On computable numbers, with an application to the Entscheidungsproblem]. ''Proceedings of the London Mathematical Society''. IEEE. 1937. Vol. 2 (42). hlm. 230–265. doi:10.1112/plms/s2-42.1.230.</ref> Adalah salah satu hasil terpenting pada teori komputabilitas, karena hal itu merupakan contoh dari masalah konkret yang sama-sama mudah untuk diformulasikan dan tak mungkin diselesaikan oleh mesin Turing. Terlebih pada teori komputabilitas yang membangun dari hasil masalah terbata-bata.

	~~Teori Komputabilitas berhubungan secara pokok dengan pertanyaan-pertanyaan dari batas cakupan pada~~ di mana ~~sebuah masalah itu dapat diselesaikan oleh sebuah komputer. Pernyataan~~ bahwa [[~~permasalahan terbata-bata~~]] ~~tak bisa diselesaikan oleh~~ mesin Turing ~~Adalah salah satu hasil terpenting pada teori komputabilitas, karena hal~~ itu ~~merupakan contoh dari masalah konkret yang sama~~-~~sama mudah untuk diformulasikan~~ dan ~~tak mungkin diselesaikan oleh mesin Turing~~. ~~Terlebih pada teori komputabilitas yang membangun dari hasil masalah terbata-bata~~.		Langkah lain dalam teori komputabilitas adalah [[Teorema Rice]], di mana menyebutkan bahwa pada semua properti dari fungsi non-trivial, adalah [[logika]] di antara pada mesin Turing mengkomputasi fungsi parsial dengan properti itu.<ref>Henry Gordon Rice. ''Classes of Recursively Enumerable Sets and Their Decision Problems (Kelas-kelas Himpunan Enumerasi Rekursif dan Permasalahan Pemilihannya)''. ''Transactions of the American Mathematical Society''. American Mathematical Society. 1953. Vol. 74 (2). hlm. 358–366. doi:10.2307/1990888.</ref>

	Langkah lain dalam teori komputabilitas adalah [[Teorema Rice]], di mana menyebutkan bahwa pada semua properti dari fungsi non-trivial, adalah [[logika]] di antara pada mesin Turing mengkomputasi fungsi parsial dengan properti itu.		Teori Komputabilitas lebih dekat pada percabangan dari [[logika matematis]] disebut [[teori rekursi]], di mana menghapus batasan dari pembelajaran model komputasi yang di mana bisa disederhanakan hingga model Turing.<ref>Martin Davis. [https://archive.org/details/isbn_9780486432281 (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)]. Dover Publications. 2004. ISBN 978-0486432281.</ref> Banyak matematikawan dan ahli teori komputasional yang mempelajari pembelajaran teori rekursi akan merujuk hal itu pada teori komputasi.

	Teori Komputabilitas lebih dekat pada percabangan dari [[logika matematis]] disebut [[teori rekursi]], di mana menghapus batasan dari pembelajaran model komputasi yang di mana bisa disederhanakan hingga model Turing. Banyak matematikawan dan ahli teori komputasional yang mempelajari pembelajaran teori rekursi akan merujuk hal itu pada teori komputasi.

	=== Teori Komputasional Kompleks ===		=== Teori Komputasional Kompleks ===

	~~== Referensi ==~~


	== Pranala luar ==		== Pranala luar ==
	* [http://www.cis.upenn.edu/~giorgi/cl.html Computability Logic] - Teori komputasi interaktif		* [http://www.cis.upenn.edu/~giorgi/cl.html Computability Logic] - Teori komputasi interaktif

			== Referensi ==
			<references />

	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Teori+komputasi&oldid=28423278 Wikipedia bahasa Indonesia], revisi 28423278 (2025-11-12T07:53:38Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Teori+komputasi&oldid=28423278 Wikipedia bahasa Indonesia], revisi 28423278 (2025-11-12T07:53:38Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

			<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 28423278; atribusi sumber disertakan.

2026-08-23T04:03:16Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 28423278; atribusi sumber disertakan.

Halaman baru

'''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 (seni)|formalisme]] komputasi. Bidang teori komputasi dibagi menjadi tiga cabang besar: [[teori automata]] dan [[bahasa formal]], [[teori komputabilitas]] dan [[teori kompleksitas komputasional]], di mana dihubungkan dengan pertanyaan: ''"Apa saja kemampuan dan batasan yang dimiliki komputer?".''

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]]. Para ilmuwan mempelajari mesin Turing karena mudah untuk diformulasikan, bisa di analisis dan digunakan untuk membuktikan sebuah hasil, dan karena mesin Turing merepresentasikan model komputasi yang kuat dan "cocok" (lihat [[Church–Turing thesis]]). Hal ini sepertinya memiliki potensial kapasitas memori tak terhingga merupakan atribut yang tak disadari, tetapi pada tiap masalah logika diselesaikan oleh mesin Turing selalu membutuhkan memori yang terbatas. Sehingga, dalam prinsipnya setiap masalah yang bisa diselesaikan (dipilih untuk diselesaikan) oleh mesin Turing bisa diselesaikan oleh komputer yang 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 masalah 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 ===

Teori Automata adalah ilmu tentang mesin abstrak (atau lebih tepatnya adalah sistem atau mesin abstrak 'matematis') dan masalah 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]], 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 teoretis untuk mesin komputasi, dan digunakan untuk kemampuan komputabilitas.

==== Teori Bahasa Formal ====

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), 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 masalah yang harus di komputasi.

=== Teori Komputabilitas ===

Teori Komputabilitas berhubungan secara pokok dengan pertanyaan-pertanyaan dari batas cakupan pada di mana sebuah masalah itu dapat diselesaikan oleh sebuah komputer. Pernyataan bahwa [[permasalahan terbata-bata]] tak bisa diselesaikan oleh mesin Turing Adalah salah satu hasil terpenting pada teori komputabilitas, karena hal itu merupakan contoh dari masalah konkret yang sama-sama mudah untuk diformulasikan dan tak mungkin diselesaikan oleh mesin Turing. Terlebih pada teori komputabilitas yang membangun dari hasil masalah terbata-bata.

Langkah lain dalam teori komputabilitas adalah [[Teorema Rice]], di mana menyebutkan bahwa pada semua properti dari fungsi non-trivial, adalah [[logika]] di antara pada mesin Turing mengkomputasi fungsi parsial dengan properti itu.

Teori Komputabilitas lebih dekat pada percabangan dari [[logika matematis]] disebut [[teori rekursi]], di mana menghapus batasan dari pembelajaran model komputasi yang di mana bisa disederhanakan hingga model Turing. Banyak matematikawan dan ahli teori komputasional yang mempelajari pembelajaran teori rekursi akan merujuk hal itu pada teori komputasi.

=== Teori Komputasional Kompleks ===

== Referensi ==

== Pranala luar ==
* [http://www.cis.upenn.edu/~giorgi/cl.html Computability Logic] - Teori komputasi interaktif

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Teori+komputasi&oldid=28423278 Wikipedia bahasa Indonesia], revisi 28423278 (2025-11-12T07:53:38Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.