the study of exploring the fundamental capabilities and limitations of computers. commonly broken down into three sections: automata, computability, and complexity.
automata theory
at a very very fundamental level, computers solve problems. how do we encode problems so that computers can read and respond to them? we formalize a problem as a computational problem with clearly specified inputs and outputs. we can then analyze the problem with questions like:
- can the problem be solved at all with a computer?
- how efficiently can it be solved?
- how can we be convinced that the solution is correct?
limits of computability
the theory of computation deals with understanding the limits of computability independent of any programming languages or computing problems. this means we base our models of computation in the language of mathematics, and study their properties mathematically.
computability theory
development of ideas that help us classify whether problems are solvable or unsolvable. can a computer determine whether a mathematical statement is true or false? the answer is no.
complexity theory
how fast or slow can we possibly solve a problem? we’ve developed ideas that allow us to classify problems as computationally easy and hard.