Theory of Computation

Theory of computation is a field in computer science that is concerned with the study of how problems can be solved efficiently by using algorithms. Two main areas of study related to it are logic and logic in mathematics which help in understanding the way how the algorithm should work.

According to Oded Goldreich “The Theory of Computation aims at understanding the nature of computation, and specifically the inherent possibilities and limitations of efficient computations. The Theory of Programming is concerned with the actual task of implementing computations (i.e., writing computer programs).”

In the last century theory of computation has become a liberated academic discipline and was separated from mathematics to a more individual part of computer science. These computer scientists try to answer how to solve a problem efficiently and do the different automata model have the capability to problem – solve effectively. Some developers of the theory of computation were Alonzo Church, Kurt Gödel, Alan Turing, Stephen Kleene, John von Neumann and Claude Shannon.

Nowadays computer scientists use Turing machine model for computation as it is easy to analyze and used to prove results. Another concept dealt in this field is ‘The Computability theory’, it is concerned with the subject of the degree to which an issue is resolvable on a computer or not. It is further divided into two main aspects which question how many steps are needed perform a task (time complexity) and how much memory is expected to complete the calculation (space complexity).

Complexity theory studies whether a problem can be solved and how efficiently the problem can be solved. Computability theory questions mainly with what extent to a problem can be solved on the computer. Computability theory is also closely related to the branch of mathematical logic called recursion theory. Recursion theory are motivated by the question: “given sets A and B of natural numbers, is it possible to effectively convert a method for deciding membership in B into a method for deciding membership in A? If the answer to this question is affirmative then A is said to be reducible to B.”(wikipedia). Many mathematicians and theorists still refer to recursion theory as computability theory.

Additionally, some areas like cryptography, computation learning theory, etc. cannot be categorized into the divisions of Theory of Computation.

In conclusion, Theory of Computation is a very important branch of computer science. Many questions are raised every day and theory of computation is very important to solve those past and future problems.

Questions on ‘Theory of Computation’:

1. How do we determine if there is an answer to a problem or not?

2. Is there any other model/machine (like the Turing machine) used by computer scientists?

3. Is there any limitation in this theory?

4. What kind of research is done in this field?

Links related to Theory of Computation:

https://en.wikipedia.org/wiki/Theory_of_computation

http://www.cis.upenn.edu/~jean/gbooks/cis51108sl1.pdf

http://cs.stanford.edu/people/eroberts/courses/soco/projects/2004-05/automata-theory/basics.html

http://www.sanfoundry.com/automata-theory-basic-definition/

http://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf