Theory Of Computation

Theory of Computation or Theory of Automata is the core area of computer engineering and computer science, it is the branch that aims to attempt the deep understanding of computational processes by means of effectively solving the problems via mathematical models, techniques  and tools. This understanding is important for its applications that include various models of computation like algorithm, VLSI design and compiler, to the creation of intelligent technology, cognitive psychology, and philosophy.

In a more layman term we redescribe it as a part of theoretical Computer Science which is mainly concerned with the study of how problems can be solved using algorithms. Therefore, we can infer that it is very important to the study of logic and mainly logic within mathematics. These studies are used to understand the proper way an algorithm is meant to work, and to actually prove it works through analyzing the problems that may arise with the technique used and finding solutions to these problems that arise. It is quite a huge field of study but it is split up into three different parts i.e. automata theory, computability theory, and computational complexity theory.

In this specific field of study, computer scientists and engineers work using a model of computation. The most preferred model nowadays is the Turing machine model. This is because it is fairly simple and can be analyzed and used to prove results. The three sectors of theory of computation mentioned before deal with different studies; the Automata theory is the study of abstract mathematical systems or machines and also the computational problems that can be solved using these machines, these machines go by the name of automata. The Computability theory deals with the question of the extent to which a problem is solvable on a computer. Computational complexity theory takes under consideration whether a problem can be solved at all on a computer, as well as how efficiently that problem can be solved.

The two main aspects in this process are: Time complexity and Space complexity as studied by the beginners in the computer programming field. Time complexity is how many steps it takes to perform a computation or to solve a problem, and Space complexity is how much space or memory is needed to carry out that computation.

A model of computation and processing is the definition of the operations used in computation. It is used to calculate the complexity of an algorithm in execution time and memory space. Examples of models of computation other than Turing machines are finite state machines, combinatory logic, lambda calculus,  recursive functions, and abstract rewriting systems. In the field of runtime analysis of algorithms, we usually specify a computational model in terms of primitive operations permitted. The study of models of computation involves numerous other fields and each one has its own specifications and definition. Overall, theory of computation allows us to explore the nature of computations in a more deep state to understand new concepts and apply them to computer science.