Computation
From Simple English Wikipedia, the free encyclopedia
The Theory of Computation is a branch of Mathematics. Generally it is seen as belonging to Computer science. The field of study of this subject is to see if a certain problem can be solved by a computer. If this is the case, then the question is to know if it can be solved in an efficient way.
There are two major branches in it. The first is computability theory. It looks to see if a certain problem can be solved by a computer. Since this is a theoretical field of study, no real computers are used. They are replaced by a system called the Turing machine.
Once it is known if such a solution exists, computer scientists want to know if it can be found, and perhaps how it can be improved. This field of study is covered by the complexity theory. That theory has developed concepts to compare different methods of solving a problem to one another. Such methods are usually called algorithms. This is similar to comparing cooking recipes and seeing which of two recipes is easier to do.
