What is the Theory of Computation?

The Theory of Computation is a branch of computer science and mathematics that focuses on determining problems that can be solved mechanically, using an algorithm or a set of programming rules. It is also concerned with the efficiency at which the algorithm can perform the solution.

In simple terms, the Theory of Computation answers these questions:

• What problems can the machine solve? What problems can’t it solve?
• How fast can a machine solve a problem?
• How much memory space does a machine need to solve a problem?

To answer these questions, computer scientists use a model of computation, which is a computer simulation for the algorithm being developed. The Turing machine is among the most used models of computation.