Theory of computation


The theory of computation is a field in computer science about how to solve problems efficiently using algorithm. It is divided into three major branches: automate theory and language, computability theory and computational complexity theory. It became an independent academic discipline in the last century and become an out growth of mathematical logic and information theory.


Computer scientists use specific models of computation to solve problem. Nowadays one preferred model is Turning machin model. Compared to other models, Turning machine model can be easily analysed and worked out the result, which create a great possibility for computer scientists to work on the three section of theory of computation. Automate theory aims to study abstract machines and automate. It works on the sequence of inputs. Computability theory is related to the study to figure out if the specific problems could be solved by computers. And computational complexity theory focus on classifying computational problems based on their difficulty.


As the above mention, one purpose of theory of computation is to find out the way to solve computational problems efficiently. For example,it is easy to multiply integers, but it seems hard to take the product and factor it into its prime components. Of course this problem also creates many related problem. Rather than classifying the problems, another purpose the theory of computation works for is to verify the validity of a solution. Again, this also create many related problems.


Even not every student will do the research in the field of the theory of computation, it is recommended for them to get to know it. It tells us how to understand the elementary ways a computer can be made to think. And this topic can be related to many fields in computer science, such as artificial intelligence and natural language processing. In general, the theory of computation is a “theory” of computer science rather than “application”. It focus on the abstract things to figure the “core” of different problems computers are facing by figure out if the problems can be solved, how to solve and how to do it in a efficient way.


What this aspect attracts me most is that it can help scientists to develop and solve the problem efficiently. And I really  interest in it because I believe it can improve my understanding in the fields I am going to do, like computer vision and machine learning.


In general, this topic really need a lot of time and effort to study, and it also will give you a good pay.


Question 1: What is the differences between different models?

Question 2: How it affect computer scientists’ ways to think?

Question 3: How it can help people to understand different fields in computer science?