Theory of Computation — What Can Be Computed?

The theory of computation studies the fundamental capabilities and limitations of computing machines. It tells us which problems can be solved and how efficiently.

Three Core Areas

• Automata theory — finite automata, regular languages.
• Computability theory — Turing machines, decidability, halting problem.
• Complexity theory — time and space classes, P, NP, NP-complete.