The Theory of Computation
Theory of Computation
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
- 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:
is the study of abstract computational devices.
Abstract devices are (simplified) models of
computations.Computations happen everywhere: On your laptop, on your
phone, in nature, …
theory deals primarily with the question of the
extent to which a problem is solvable on a computer. The
the halting problem cannot be solved by a Turing
is one of the most important results in
theory, as it is
an example of a concrete problem that is both
easy to formulate and impossible to solve
using a Turing machine.
computability theory builds on the halting
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:
and how many steps does it take to perform
Space complexity:and how much memory is required to
perform that computation
Why do we study computional theory?
- • Deeper understanding of what is a
- • Foundation of all modern computers.
• Philosophical implications
search: theory of pattern matching.
theory of finite state automata.
of context free grammars.
theory of information.
What are the benefits of
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
Natural Language Processing
that involved building
Finite State machines
also known as Finite
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.
1)Design and Analysis of Algorithms
3)Logic in Computer Science
6)Randomness in 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:
to the Theory Of Computation
about computation theory
Frequently asked questions:
1_Is the theory of Computation
only related to researchs?
I need to learn "Theory of Automata" ?