Theory of Computation


"Our best theories are not only truer than common sense, they

make more sense than common sense."


~David Deutsch


References / Learn More



[1] Interesting book to buy

[2] An Intro. to Theory of Computation

[3] The P vs NP Problem

[4] Wikipedia Page

[5] Theory of Computation - MIT


Theory of Computation


The Theory of Computation is yet another scientific discipline under the branch of Computer Science. It can be viewed as the subdivision that takes care of solving problems efficiently and effectively with the help of models of computation and complex algorithms. The theory of computation involves a lot of mathematics and logic involved, hence it acquired its “independence” from mathematics in the last century and became its own discipline. The forerunners of the subject include researchers such as Alonzo Church, Kurt Godel, Stephen Kleene among several others.



The Theory of Computation is typically allied with the study of common properties of computation. It aims to comprehend the nature of proficient computation. It is also concerned with finding the most efficient procedures for solving specific problems.



The Theory of Computation can further be isolated into two fundamental groups: complexity theory and algorithms. The former spotlights on computational assets while the latter focuses on the activities to be taken care of.



Moreover, there are a few ranges of Theory of Computation that can't be sorted into the above divisions. Samples of such incorporate, cryptography, distributed computing and computation learning hypothesis.



Theory of Computation is a dynamic branch of computer science. It is a vast field and there are many new problems for which efficient solutions are yet to be found that pop up every day.



The Theory of Computation is a very broad section of computer science. It is a very interesting field and there are numerous new issues that arise daily for which proficient arrangements are yet to be found.



Questions on my mind



1. What is the differene between various models of computation?

2. Is there or will there ever be a way to solve highly complex problems in Computer Science (for instance; the P vs NP problem)?



Amer Ahmad
CMU-Q Computer Science
Class of 2019