Theory of computation
Theory of computation is a branch of computer science that deals with how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into three major branches: automata theory, computability theory, and complexity theory.
Automata Theory[edit]
Automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata. Automata comes from the Greek word αὐτόματα meaning "self-acting". Automata Theory is the study of self-acting or self-moving machines.
Computability Theory[edit]
Computability theory revolves around the idea of the amount of resources required to solve a particular problem. This field of theory of computation involves the study of the extent and limitations of what can be computed. It is closely related to the Church-Turing thesis which hypothesizes the capabilities of a mechanical computation model.
Complexity Theory[edit]
Complexity theory, a sub-branch of the theory of computation, focuses on classifying computational problems according to their inherent difficulty. It also deals with related topics such as approximation algorithms.
Conclusion[edit]
The theory of computation is a fundamental area in computer science that has significant implications for the development of new algorithms and the advancement of technology. It provides a deep understanding of computation by abstracting it to a theoretical level, allowing for a more profound understanding of what can and cannot be computed, and how efficiently computations can be performed.
Theory_of_computation[edit]
-
Chomsky hierarchy
-
Complexity subsets in PSPACE
