Theory Of Computation

Theory of Computation is a branch that deals with how efficiently problems can be solved on a model of computation. Model of computation is a set of allowable operations along with their respective cost.
It is used for measuring the complexity of the algorithm and the memory space the algorithm takes during execution. This field of research was started by mathematicians and logicians in the 1930's.
Theory of computation is widely divided into three subparts:-
1)Computational Complexity Theory
2)Computability Theory
3)Automata Theory and Language

Complexity theory:- the theory helps us to classify a problem according to the degree of difficulty. This theory raises the question “What makes some problems computationally hard and other easy?”.
In this theory a problem is classified as a “hard” or “easy depending upon whether it can be efficiently solved. Thus, an example of an easy problem is searching for a name in a telephone directory.
Whereas, a difficult problem is factoring a three hundred digit integer into its prime factor.

Computability theory:- This theory classifies problem as solvable or unsolvable. The other view of the computability theory is which extent a problem can be solved.
In the 1930’s it was discovered that there are certain mathematical problems which cannot be solved by computers. For example:- is an arbitrary mathematical statement true or false?
For answering such questions we need to first define the definition of computer, algorithm and computation.

Automata theory:- This theory deals with the properties of the different computation model.
1)Finite automata- This has a great application in text processing ,compilers and hardware design.
2)Context free grammars- its main aim is to define programming language and artificial intelligence.
3)Turing machines- This machine Makes an abstract model of a real computer like we have it at our home.

Applications of theory of computation can be found in the present world. It plays an important role in cloud computing and virtual machines.