Theory of Computation
The theory of computation consists of the fundamental mathematical properties of computer hardware, software and other applications. There are three central areas of the theory of computation, namely, automata, computability and complexity. All of these areas in fact lead us to think about the key capabilities and limitations of computers. It is somewhat hard to imagine that computers have limitations. Can we compute “everything”? The answer to that is a NO!
Mathematical logicians in the 1930s were trying to figure out what does “computation” really mean and the technological advances since then have had a positive impact on our ability to compute.It is interesting to note that the question “What are the fundamental capabilities and limitations of computers?” has a different interpretation in each of the above -mentioned there areas-automata, computability and complexity and something which is even more interesting to note is that the answers vary from one interpretation to the other!
Let’s consider the complexity theory. The central question asked in this area is “What makes some problems computationally hard and others easy? “ As surprising as it may seems, the answer to this question is not known yet, although an extensive research about that has been going on for the past 35 years. Let’s take a look at some examples; an easy computer problem is arranging a list of integers in ascending order. Compare that to a scheduling of classes of an entire university. Indeed, the scheduling problem is a tougher problem than the sorting one. One of the most important achievements of the complexity theory is the discovery of a scheme to classify problems according to their computational difficulty, analogous to the periodic table of elements which classify elements according to their chemical properties.The theories of computability and complexity are related to a certain extent. Let me explain…The main aim in complexity theory is to classify problems into two categories, easy ones and hard ones. On the other hand, in computability theory, the aim to classify the problems as those that can be solved and those that cannot. As a matter of fact, computability theory introduces numerous concepts used in the complexity theory.Automata theory deals a great deal with the definitions and properties of mathematical models of computation. It introduces concepts related to other non-theoretical aspects of computer science. Some examples of such models are the finite automaton which is used in text processing, compilers and hardware design, and the context-free grammar which is used in programming languages and artificial intelligence.
Here are some links where tou can find more information
How is the field of cryptography affected by the complexity theory?
Can you explain the link between the problem of determining whether a mathematical statement is true or false and the computability theory?
How does finite automaton work?
Photo Credit: www.contrib.andrew.cmu.edu