Theory of Computation
What are the fundamental capabilities and limitations of computers?
Theory of computation is study of the nature and analysis of computations. Here we study concepts like time complexity and different model of computations and how their computing powers differs. Also what are different class of problems based on how they can be solved.
Field is divided into three major branches
- Automata theory and formal languages
- Computability Theory
- Computational Complexity Theory
In order to study computations we use what are called models of computation, like turing machine. Turing machine is used because it is easy to formulate and can be analyzed to prove results.