In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation using an algorithm, how efficiently they can be solved and to what degree (e.g., approximate solutions versus precise ones).
Teori komputasi adalah cabang ilmu komputer dan matematika yang membahas apakah dan bagaimanakah suatu masalah dapat dipecahkan pada model komputasi, menggunakan algoritma.
The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".
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?".
In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called a model of computation.
Untuk melakukan studi komputasi dengan ketat, ilmuwan komputer bekerja dengan abstraksi matematika dari komputer yang dinamakan model komputasi.
There are several models in use, but the most commonly examined is the Turing machine.
Ada beberapa model yang digunakan, tetapi yang paling umum dipelajari adalah mesin Turing.
Computer scientists study the Turing machine because it is simple to formulate, can be analyzed and used to prove results, and because it represents what many consider the most powerful possible "reasonable" model of computation (see Church–Turing thesis).
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.
It might seem that the potentially infinite memory capacity is an unrealizable attribute, but any decidable problem solved by a Turing machine will always require only a finite amount of memory.
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.
So in principle, any problem that can be solved (decided) by a Turing machine can be solved by a computer that has a finite amount of memory.
Jadi pada dasarnya setiap masalah yang dapat dipecahkan (diputuskan) oleh meisn Turing dapat dipecahkan oleh komputer yang memiliki jumlah memori terbatas.
The theory of computation can be considered the creation of models of all kinds in the field of computer science.
Teori komputasi bisa dijadikan penciptaan sebuah model dari seluruh bidang ilmu komputer.
Therefore, mathematics and logic are used.
Maka, matematika dan logika digunakan.
Some pioneers of the theory of computation were Ramon Llull, Alonzo Church, Kurt Gödel, Alan Turing, Stephen Kleene, Rózsa Péter, John von Neumann and Claude Shannon.
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.
Automata theory is the study of abstract machines (or more appropriately, abstract 'mathematical' machines or systems) and the computational problems that can be solved using these machines.
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.
These abstract machines are called automata.
Mesin-mesin abstrak ini disebut sebagai automata.
Automata comes from the Greek word (Αυτόματα) which means that something is doing something by itself.
Automata (Αυτόματα) berarti sesuatu yang melakukan sesuatu dengan sendirinya.
Automata theory is also closely related to formal language theory, as the automata are often classified by the class of formal languages they are able to recognize.
Teori Automata sangat dekat dengan teori bahasa formal, Automata sering diklasifikasikan oleh beberapa kelas dari bahasa formal karena mereka memiliki kemampuan untuk "mengenal".
An automaton can be a finite representation of a formal language that may be an infinite set.
Sebuah Automaton bisa merupakan representasi bahasa formal yang terbatas yang bisa merupakan himpunan tak terbatas.
Automata are used as theoretical models for computing machines, and are used for proofs about computability.
Automata digunakan sebagai model teoretis untuk mesin komputasi, dan digunakan untuk kemampuan komputabilitas.
Formal language theory is a branch of mathematics concerned with describing languages as a set of operations over an alphabet.
Teori Bahasa adalah cabang dari matematika yang mempelajari tentang menerangkan bahasa-bahasa sebagai bagian dari operasi-operasi atas Alfabet(bahasa formal).
It is closely linked with automata theory, as automata are used to generate and recognize formal languages.
Teori ini sangat dekat dengan teori Automata, karena Automata digunakan untuk membuat dan mengenal bahasa formal.
There are several classes of formal languages, each allowing more complex language specification than the one before it, i.e. Chomsky hierarchy, and each corresponding to a class of automata which recognizes it.
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.
Because automata are used as models for computation, formal languages are the preferred mode of specification for any problem that must be computed.
Karena Automata digunakan sebagai model-model dari komputasi, bahasa formal lebih disarankan sebagai mode spesifikasi untuk semua masalah yang harus di komputasi.
Computability theory deals primarily with the question of the extent to which a problem is solvable on a computer.
Teori Komputabilitas berhubungan secara pokok dengan pertanyaan-pertanyaan dari batas cakupan pada di mana sebuah masalah itu dapat diselesaikan oleh sebuah komputer.
The statement that the halting problem cannot be solved by a Turing machine is one of the most important results in computability theory, as it is an example of a concrete problem that is both easy to formulate and impossible to solve using a Turing machine.
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.
Another important step in computability theory was Rice's theorem, which states that for all non-trivial properties of partial functions, it is undecidable whether a Turing machine computes a partial function with that property.
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
Computability theory is closely related to the branch of mathematical logic called recursion theory, which removes the restriction of studying only models of computation which are reducible to the Turing model.
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.