The theory of computing forms the mathematical foundation for studying computation, independent of a specific situation, piece of hardware or programming language. It gives formal definitions for what an “algorithm” is, what a “problem” that an algorithm solves is and what it means for an algorithm to solve a problem “efficiently.” The theory of computing enables us to prove that certain problems cannot be solved by any algorithm, and others, though solvable, cannot be solved efficiently.
