The theory of computation is a mathematical science that studies the fundamental capabilities and limitations of computing machines. The central question that it strives to answer is "What can be computed?". Traditionally the subject is subdivided into three areas: automata theory, computability theory and complexity theory.

Automata theory studies various mathematical models of computation, with a main focus on relatively weak but fast and simple models. The most typical and popular models of this sort are finite automata (computing devices with only a finite amount of memory) and pushdown automata (devices with an infinite but limited-access memory). These models of computation are most directly related to certain natural and simple classes of formal languages such as regular or context-free languages. Hence, the official scope of automata theory is typically extended to studies of formal languages.

Computability theory studies what can and cannot be computed in principle with strongest possible computers. According to the famous Church-Turing thesis, the mathematical model of computation called Turing machine adequately captures our intuition of "the strongest possible computer".

While computability theory is only concerned with the problem of computability in principle, complexity theory focuses on the efficiency of computations. The typical questions that it asks are "How many steps does a computation take?" (time complexity) and "How much memory does a computation require?" (space complexity). This area abounds with very challenging and long-standing open problems, including the "million dollar problem" regarding whether P=NP.