The Theory of  Computation

The Theory of computationThe Theory of  Computation

General information

  • The Theory of Computation is a scientific discipline concerned with the study of general properties of computation be it natural, man-made, or imaginary. Most importantly, it aims to understand the nature of efficient computation. In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm. That is how wikipedia defines "The theory of computation".
  • This field of research was started by mathematicians and logicians in the1930’s, when they were trying to understand the meaning of a “computation”.. The research that started in those days led to computers as we know them today.Nowadays, the Theory of Computation can be divided into the following three areas: Complexity Theory, Computability Theory, and Automata Theory.
  • Areas of theory of computional:
  • 1_Automata theory:
Automata theory is the study of abstract computational devices. Abstract devices are (simplified) models of real computations.Computations happen everywhere: On your laptop, on your cell phone, in nature, …

2_Computability theory:

Computability theory deals primarily with the question of the extent to which a problem is solvable on a computer. The statement that the halting problem cannot be solved by a Turing machine is one of the most important results in computability theory, as it is an example of a concrete problem that is both easy to formulate and impossible to solve using a Turing machine. Much of computability theory builds on the halting problem

3_Complexity theory:

Complexity theory considers not only whether a problem can be solved at all on a computer, but also how efficiently the problem can be solved. Two major aspects are considered:

1.     Time complexity: and how many steps does it take to perform a computation .

2.    Space complexity:and how much memory is required to perform that computation.


Why do we study computional theory?

In theory . . .
 Deeper understanding of what is a computer and computing.
• Foundation of all modern computers.
Pure science.
• Philosophical implications

In practice . . .
Web search: theory of pattern matching.
Sequential circuits: theory of finite state automata.
Compilers: theory of context free grammars.

Cryptography: theory of computational complexity.

Data compression: theory of information.

What are the benefits of studying theory of computation ?
 Theory of computation teaches you about the elementary ways in which a computer can be made to think.
 There is a great deal of work that was made possible in the area of Natural Language Processing that involved building Finite State machines also known as Finite State Automata

Understand the mathematical laws governing efficient computation, and Apply this understanding to address problems arising in other parts of computer science and mathematics, and in other fields such as neuroscience and physics.

Research Areas:
1)Design and Analysis of Algorithms
2)Computational Complexity
3)Logic in Computer Science
4)Error-Correcting Codes
6)Randomness in Computation
7)Quantum Computation

I feel that the theory of computation is the main core of computer science, as it shows to us the relation between mathematics and computer science. Making computer science the new mathematics.


Useful websites for further information:

1_Introduction to the Theory Of Computation


3_Lecture about computation theory

Frequently asked questions:

1_Is the theory of Computation only related to researchs?

2_WHY I need to learn "Theory of Automata" ?