01
Automata
Automata theory studies abstract machines and the languages they recognize. Finite automata recognize regular languages, while more expressive models such as pushdown automata correspond to context-free languages.
02
Turing Machines
The Turing machine is a foundational formal model for general computation. Computability theory asks which problems can be solved by an algorithm at all.
03
Complexity Classes
Complexity theory categorizes problems according to the resources required to solve or verify them.
P ⊆ NP
Major questions such as whether P equals NP concern fundamental limits on efficient computation.