Theory of computation

Summary

The theory of computation studies which problems can be solved by an algorithm and how many resources a solution needs. It makes the idea of an algorithm precise through a model of computation, such as the Turing machine. Its three main parts are automata theory, computability theory and computational complexity theory. It gives the mathematical limits of what computers can do, independent of any real hardware.