Introduction to Theory of Computation
Theory of computation is the branch of computer science that focuses on understanding the nature and capabilities of computers. It also deals with the efficiency of computers solving problems on a model of computation. Theory of Computation is the study of what kind of things can be computed mechanically. How fast it can be computed and how much space it takes. The model of computation I am referring to here is a simple computer system, not exactly but its mathematical model. That means the theory of computation deals with what can and what cannot be computed by the model of computation (computers).
The field is divided into three major branches.
- Automata theory
- Computability theory
- Computational complexity theory.
A question links these three things.
“What are the fundamental capabilities of computers and what are the limitations of computers?”
In each of these branches, the question is interpreted differently, and the answer varies accordingly.
To perform a rigorous study of computation, computer scientists work with a mathematical model of computers called the “Model of Computation”. There are several models in use but the most used is the “Turing machine”.
Automaton Theory
Automata theory is the study of abstract computational mathematical machines and the computational problems that can be solved using these machines.
The abstract machines are called Automata., (meaning something does something by itself). An automaton is a finite representation of a formal language. (formal language can be an infinite set). Automata are used as theoretical models for computing machines and used as proof of computability.
Automata theory deals with definitions and properties of mathematical models of computation. In automata, theory is an excellent place to begin the study of the theory of computation.
Computability theory and Complexity theory
During the first half of the 20th century Kurt Godel and Alan Turing discovered that certain basic problems cannot be solved by computers. One example of this phenomenon is the problem of determining whether a mathematical statement is true or false.
Among the consequences of this profound result was the development of ideas concerning theoretical models of computers that eventually helped lead to the construction of actual computers.
The theories of computability and complexity are closely related. Complexity theory classifies problems as easy ones and hard one’s whereas in computability theory the classifies problems as solvable and those that are not.
